Меню

Составить таблицу истинности булевой функции



Таблица истинности

Инструкция . При вводе с клавиатуры используйте следующие обозначения:

Клавиша Оператор
! ¬ Отрицание (НЕ)
| | Штрих Шеффера (И-НЕ)
# Стрелка Пирса (ИЛИ-НЕ)
* & Конъюнкция (И)
+ v Дизъюнкция (ИЛИ)
^ Исключающее ИЛИ, сумма по модулю 2 (XOR)
@ Импликация (ЕСЛИ-ТО)
% Обратная импликация
= ≡ (

bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис.

Правила ввода логической функции

  1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
  2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
  3. Максимальное количество переменных равно 10 .

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики — алгебры логики. В алгебре логики можно выделить три основные логические функции: «НЕ» (отрицание), «И» (конъюнкция), «ИЛИ» (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:

  • словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
  • описание функции алгебры логики в виде таблицы истинности.
  • описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ:
    а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу:
    1) в таблице выбираются те строки переменных для которых функция на выходе =1 .
    2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией.
    3) полученное произведение логически суммируется.
    Fднф= X 123 ∨ Х1 x 2Х3 ∨ Х1Х2 x 3 ∨ Х1Х2Х3
    ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
    б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
    КНФ может быть получена из таблицы истинности по следующему алгоритму:
    1) выбираем наборы переменных для которых функция на выходе =0
    2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
    3) логически перемножаются полученные суммы.
    Fскнф=(X1 V X2 V X3) ∧ (X1 V X2 V X 3) ∧ (X1 V X 2 V X3) ∧ ( X 1 V X2 V X3)
    КНФ называется совершенной, если все переменные имеют одинаковый ранг.

По алгебраической форме можно построить схему логического устройства, используя логические элементы.

Рисунок1- Схема логического устройства

Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

Источник

СДНФ, СКНФ. Как построить с использованием таблицы

Как известно, все существующие логические функции обладают совершенной дизъюнктивной нормальной формой, а также совершенной конъюнктивной нормальной формой. Обозначаются они аббревиатурами СДНФ и СКНФ соответственно. Рассмотрим принципы их построения с использованием таблицы истинности, устанавливающей соответствие всех возможных вариаций логических переменных.

Основные правила при построении СДНФ

СДНФ является дизъюнкцией конституента единицы, соответствующей входящей совокупности логических переменных, при которых функция достигает показателя «1». Она удовлетворяет 3 условия:

  • Включает разные элементарные конъюнкции.
  • Конъюнкции включают разные переменные.
  • Все из элементарных конъюнкций включают в одной и той же последовательности все имеющиеся логические переменные этой ДНФ.

Привести к СДНФ можно всякую булеву формулу за исключением той, что не выступает тождественно ложной. Получению СДНФ предшествует создание таблицы истинности. Чтобы построить СДНФ следует записать произведение для каждой совокупности присутствующих переменных. Важно учесть, что логические переменные со значением «0» нужно брать с отрицанием.

Принципы построения СКНФ

СКНФ является конъюнкцией конституента нуля, соответствующих входящих логических переменных, при которых функция достигает «0». Она удовлетворяет 3 условия:

  • Включает разные элементарные дизъюнкции.
  • Дизъюнкции включают разные переменные.
  • Все из элементарных дизъюнкций включают каждую логическую переменную данной КНФ.

К такой форме возможно привести булеву формулу, за исключением той, которая не выступает тождественно истинной.

Чтобы получить СКНФ функции необходимо сначала построить таблицу истинности. При построении СКНФ по таблице следует записать сумму для каждого набора логических переменных. Обратите внимание, что переменные, имеющие значение «1» нужно брать с отрицанием.

Примеры нахождения СКНФ и СДНФ

Запишем логическую функцию по ее таблице истинности:

Источник

Составить таблицу истинности булевой функции

Добрый день! Пожалуйста, помогите разобраться с двумя задачами.
1. Для заданной булевой функции f(x1,x2,x3,x4)=V(0,2,4,5,6,9,11) составить таблицу истинности.
Не могу понять, что представляет из себя конкретно эта функция, как составить её таблицу истинности и можно ли её представить в виде выражения с переменными и лог.операциями?
2. Решить систему логических уравнений:

Прим. (+) — плюсик в кружочке Не знала, как по-другому поставить

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Написать таблицу истинности булевой функции
1. Написать таблицу истинности булевой функции f(x,y,z), заданной формулой. 2. Найти фиктивные.

Составить таблицу истинности для функции
Помогите пожалуйста составить таблицу истинности для функции: f(x;y;z)=(xz’)V(z(yVz’))

Составить таблицу истинности для заданной логической функции
господа гении прошу я совершенно ничего в этом не понимаю, сколько бы не читала. извините, что с.

Лучший ответСообщение было отмечено tashamorozz как решение

Решение

Сообщение от tashamorozz

Эта функция принимает значение 1 на наборах 0,2 и т.д. (записанных в двоичной системе счисления).

Сообщение от tashamorozz

Можно. Но если нужна лишь таблица, то не нужно.

Сообщение от tashamorozz

Из последнего уравнения сразу получаем, что y=1. Подставляем в два первых и упрощаем, используя основные законы логики.

Лучший ответСообщение было отмечено tashamorozz как решение

Решение

Сообщение от tashamorozz

Обозначение V нужно смотреть в материалах вашего курса, но скорее всего это означает функцию, которая принимает 1 на наборах 0, 2, и т.д. Номер набора нужно записать в двоичной форме из четырех цифр, чтобы получить значения отдельных аргументов. Например, , поэтому f(1,1,0,1) = 1.

По второй задаче попробуйте записать все уравнения через (сложение по модулю 2) и конъюнкцию (умножение). Так, . Далее, , поэтому . Из третьего данного уравнения y = 1, поэтому , и по условию это = 0. Отсюда . Теперь подставьте y = 1 во второе уравнение.

Сообщение от Ellipsoid

Т.е. таблица будет примерно такая?

Сообщение от Ellipsoid

Мне в дальнейшем нужна будет. Почитав форум, я смогла составить такой вид:

3D Homer, Ellipsoid, очень подробно и понятно, спасибо!

Источник

Для заданной булевой функции постройте таблицу истинности

1) Задание булевой функции таблицей истинности. Так называется таблица, состоящая из двух частей: в левой части перечисляются все наборы значений аргументов (булевы векторы пространства B n ) в естественном порядке, то есть по возрастанию значений чисел, представляемых этими векторами, а в правой части – значения булевой функции на соответствующих наборах.

Пример. Рассмотрим булеву функцию трех аргументов, называемую мажоритарной (или функцией голосования): она принимает значение 1 на тех и только тех наборах, в которых единиц больше, чем нулей (major – больший).

Так как левая часть таблицы истинности постоянна для всех функций с одинаковым числом аргументов, несколько таких функций могут быть заданы общей таблицей.

Теорема о числе булевых функций. Число различных булевых функций, зависящих от n переменных, равно 2 2 n .

Доказательство. Каждая булева функция определяется своим столбцом значений. Столбец является булевым вектором длины m=2 n , где n – число аргументов функции. Число различных векторов длины m (а значит и число булевых функций, зависящих от n переменных) равно 2 m =2 2 n . •

2) Задание булевой функции характеристическими множествами. Так называются два множества:

M 1 f, состоящее из всех наборов, на которых функция принимает значение 1, то есть M 1 f = <α B n :f(α) = 1>;

M 0 f, состоящее из всех наборов, на которых функция принимает значение 0, то есть M 0 f = <α B n :f(α) = 0>.

Пример (мажоритарная функция).

3) Задание булевой функции вектором ее значений.

Пример (мажоритарная функция).

4) Задание булевой функции матрицей Грея. Булево пространство задается матрицей Грея, и наборы (клетки матрицы), на которых булева функция f(x1, …, xn) принимает значение 1, отмечаются и называются точками.

Пример (мажоритарная функция).

5) Интервальный способ задания булевой функции. Булеву функцию f(x1, …, xn) можно задать множеством интервалов If = 1, I2, …, Ik>, объединение которых образует характеристическое множество M 1 f, то есть I1 I2 … Ik = M 1 f. Множество интервалов If называется достаточным для функции f(x1, …, xn).

Пример. Мажоритарная функция может быть задана достаточным множеством If = 1, I2, I3> интервалов:

Здесь интервалы представлены троичными векторами и изображены на матрице Грея.

В отличие от предыдущих, интервальный способ задания функций многовариантен (одну и ту же булеву функцию можно представить разными множествами интервалов).

Пример. Зададим мажоритарную функцию другим достаточным множеством I’f = 1, I2, I3, I4> интервалов:

Очевидно, что это множество интервалов избыточно: первый интервал (011) можно удалить.

Определение. Интервал назовем допустимым для булевой функции, если на всех его наборах функция равна 1.

Примеры. I1= – 1 1 – допустимый интервал для мажоритарной функции, I2= 1 0 – – не допустимый.

Определение. Интервал I назовем максимальным для булевой функции f(x1, …, xn), если он является допустимым для этой функции, и не существует другого допустимого интервала I’, такого что I I’.

Пример. I1= –11 является максимальным интервалом для мажоритарной функции, а допустимый интервал I2 = 111 не является максимальным, так как I2 I1.

Пример. Зададим мажоритарную функцию множеством I»f = 1 I2, I3> всех максимальных интервалов.

Определение. Точку булевой функции f(x1, …, xn) назовем ядерной, если она принадлежит ровно одному максимальному для этой функции интервалу. Максимальный интервал называется ядерным, если он содержит ядерную точку.

Пример. Для мажоритарной функции ядерными точками являются 011 (принадлежит только интервалу –11), 101 (принадлежит только интервалу 1 –1) и 110 (принадлежит только интервалу 11 –). Все максимальные интервалы этой функции являются ядерными. •

Очевидно, что все ядерные интервалы входят в любое достаточное множество функции, состоящее из максимальных интервалов.

6) Задание булевой функции формулами будет рассмотрено несколько позже.

Источник

Логические выражения и таблица истинности

Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.

Логическое выражение — составные высказывания в виде формулы.

Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак « =».

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице по формуле m=2 n , где n — количество переменных;

3. подсчитать количество логических операций в формуле;

4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;

5. определить количество столбцов: число переменных + число операций;

6. выписать наборы входных переменных;

7. провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в пункте 4 последовательностью.

1. разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2. разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3. продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Пример 1. Для формулы A/\ (B \/ ¬B /\ ¬C) постройте таблицу истинности.

Количество логических переменных 3, следовательно, количество строк — 2 3 = 8.

Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

Пример 2. Определите истинность логического выражения F(А, В) = (А\/ В)/\(¬А\/¬В) .

1. В выражении две переменные А и В (n=2).

2. m строк=2 n , m=2 2 =4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А\/ В; 2) ¬А; 3) ¬В; 4) ¬А\/¬В; 5) (А\/ В)/\(¬А\/¬В).

5. К столбцов=n+5=2+5=7 столбцов.

Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.

Пример 3. Построёте таблицу истинности для логического выражения

  1. В данной функции три логические переменные – А, В, С
  2. количество строк таблицы = 2 3=8
  3. В формуле 3 логические операции.
  4. Расставляем порядок действий
  1. количество столбцов таблицы = 3 + 3 = 6

Пример 4. Определите истинность формулы: F = ((С \/В) => В) /\ (А /\ В) => В.

Построим таблицу истинности этой формулы.

Ответ: формула является тождественно истинной.

Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

Решение (вариант 1, через таблицы истинности ):

Чтобы решить данную задачу можно построить часть таблицы истинности для каждой из четырех функций, заданных в ответе для заданных наборов входных переменных, и сравнить полученные таблицы с исходной:

Очевидно, что значения заданной функции F совпадают со значениями выражения X\/ Y\/¬ Z. Следовательно, правильный ответ – 3.

Решение (Вариант 2):

Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.

Рассмотрим данный конкретный пример:

1) первое заданное выражение ¬X/\¬Y/\Z = 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;

2) второе заданное выражение ¬X\/¬Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы;

3) третье выражение X\/Y\/¬Z соответствует F при всех предложенных комбинациях X,Y и Z;

4) четвертое выражение X\/Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Источник

Читайте также:  Таблица красные и белые гражданская война причины победы