Онлайн таблица истинности логического выражения. Основные двоичные функции

Выбираем строки, где
и выписываем конъюнкции всех переменных, при чем, если переменная в этом наборе равна 1, то записываем ее саму, а если переменная = 0, то ее отрицание.

Для данного примера

коньюнкция этих дизъюнкций и будет искомой формулой:

Определение: Конъюнкция называетсяэлементарной , если все переменные, входящие в нее, различны. Количество букв, входящих в элементарную конъюнкцию или элементарную дизъюнкцию, называетсярангом.

Число 1 считается элементарной конъюнкцией ранга 0. Переменная считается элементарной конъюнкцией или элементарной дизъюнкцией ранга 1. Число 0 считается элементарной дизъюнкцией ранга 0. Любую конъюнкцию переменных, не являющуюся тождественно ложной, можно привести к виду элементарной, а любую дизъюнкцию букв, не являющуюся тождественно истинной, также можно привести к виду элементарной. Для этого надо применить свойства коммутативности, идемпотентности и ассоциативности конъюнкции и дизъюнкции.

Строго доказано, что любую формулу булевой алгебры можно выразить с помощью операций , &,. Интуитивно этот факт очевиден, вспомним алгоритм составления формулы по таблице истинности. При этом мы используем только эти операции. Такая форма записи называетсядизъюнктивной нормальной формой (ДНФ). Это своеобразный механизм нормализации формул алгебры логики.

Определение: ДНФ – это дизъюнкция различных элементарных конъюнкций (т.е. каждая конъюнкция состоит из элементарных высказываний или их отрицаний).

Аналогично определяется КНФ – коньюктивная нормальная форма.

Определение: Если в ДНФ все элементарные конъюнкции имеют один и тот же ранг, равный числу переменных, от которых зависит ДНФ, то она называетсясовершенной (СДНФ).

Теорема. Для любой функции, не являющейся тождественно ложной, существует и притом единственная СДНФ.

Следствие . Любую булеву функцию, не являющуюся тождественно ложной можно представить в виде суперпозиции&,,, причем отрицание относится только к переменным.

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

Системы {&,,}; {,}; {&,},{/} – являются функционально полными

{&,} – функционально неполная.

Мы примем эти факты без доказательства, и решая задачи, будем стараться любую формулу представить с помощью {&,,}. Позже мы более подробно обсудим вопрос функциональной полноты и неполноты системы операций.

Тема 1.7. Методы упрощения логических выражений. Методы решения логических задач.

Рассмотрим пример решения логической задачи.

Пример :

После обсуждения состава участников экспедиции решено, что должны выполняться два условия.

Если поедет Арбузов, то должны ехать Брюквин или Вишневский

Если поедут Арбузов и Вишневский то поедет Брюквин

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

Введём переменные и соответствующие им элементарные высказывания.

- поедет Арбузов

- поедет Брюквин

- поедет Вишневский

Тогда выработанные условия формирования экспедиции будут выглядеть следующим образом:

Составим общую формулу и упростим выражение

т.е. если поедет Арбузов, то поедет Брюквин.

Пример:

Если завтра будет хорошая погода, то мы пойдем на пляж или поедем в лес. Составим формулу нашего поведения на завтра.

– хорошая погода

– мы пойдем на пляж

– мы поедем в лес

Теперь построим отрицание этой фразы

т.о. получим высказывание "Завтра будет хорошая погода, и мы не пойдем в лес и на пляж.

Желающие могут построить таблицу истинности и проверить это утверждение.

Пример :

По подозрению в совершенном преступлении, задержаны Браун, Джон и Смит. Один из них уважаемый в городе старик, второй чиновник, а третий известный мошенник. В ходе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом лгал.

Вот что они говорили:

Браун: Я совершил это. Джон не виноват. (Б&Д)

Джон: Браун не виноват. Преступник Смит. (Б&С)

Смит: Я не виноват. Виноват Браун (С&Б)

Опишем эти высказывания формально:

- преступление совершил Браун

- преступление совершил Джон

- преступление совершил Смит

Тогда их слова описываются следующими выражениями:

Браун:

Джон:

Смит:

Т.к. по условиям задачи две из этих &ложны и одна истинна, то

Составим таблицу истинности

Остается только случай 2 , т.е. преступник Смит, и оба его высказывания ложны.

следовательно– ложно и- истинно

= 1 – Джон уважаемый старик

Остается, что Браун чиновник, и поскольку – ложно, то– истинно.

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

Пример :

Упражнение:

Решение логических выражений принято записывать в виде таблиц истинности – таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных.

При составлении таблицы истинности для логического выражения необходимо учитывать порядок выполнения логических операций , а именно:

1. действия в скобках,
2. инверсия (отрицание ),
3. & (конъюнкция ),
4. v (дизъюнкция ),
5. => (импликация ),
6. <=> (эквивалентность ).

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

1. Выяснить количество строк в таблице (вычисляется как 2 n , где n – количество переменных + строка заголовков столбцов).

2. Выяснить количество столбцов (вычисляется как количество переменных + количество логических операций).

3. Установить последовательность выполнения логических операций.

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

5. Заполнить таблицу истинности по столбцам.

6. Записать ответ.

Упражнение 8

Постройте таблицы истинности для следующих логических выражений:

1. F =(Av B )&(¬ A& ¬ B).

2. F = X&¬ Yv Z.

Проверьте себя (эталон ответов)

Обратите внимание!

Тавтология - тождественно истинная формула истина " ("1

Противоречие - тождественно ложная формула , или формула принимающая значение "ложь " ("0 ") при любых входящих в нее значениях переменных.

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

Определение 1

Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.

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

Определение 2

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

Определение 3

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

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

Рисунок 1.

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

Алгоритм построения таблицы истинности логической функции

Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка) , $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.

Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.

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

Рисунок 2.

Пример 1

Составить таблицу истинности логического выражения $D=\bar{A} \vee (B \vee C)$.

Решение:

Определим количество строк:

кол-во строк = $2^3 + 1=9$.

Количество переменных – $3$.

1. инверсия ($\bar{A}$);
2. дизъюнкция, т.к. она находится в скобках ($B \vee C$);

3. дизъюнкция ($\overline{A}\vee \left(B\vee C\right)$) – искомое логическое выражение.

   Кол-во столбцов = $3 + 3=6$.

Заполним таблицу, учитывая таблицы истинности логических операций.

Рисунок 3.

Пример 2

По данному логическому выражению построить таблицу истинности:

Решение:

Определим количество строк:

Количество простых выражений – $n=3$, значит

кол-во строк = $2^3 + 1=9$.

Определим количество столбцов:

Количество переменных – $3$.

Количество логических операций и их последовательность:

1. отрицание ($\bar{C}$);
2. дизъюнкция, т.к. она находится в скобках ($A \vee B$);
3. конъюнкция ($(A\vee B)\bigwedge \overline{C}$);
4. отрицание, которое обозначим $F_1$ ($\overline{(A\vee B)\bigwedge \overline{C}}$);
5. дизъюнкция ($A \vee C$);
6. конъюнкция ($(A\vee C)\bigwedge B$);
7. отрицание, которое обозначим $F_2$ ($\overline{(A\vee C)\bigwedge B}$);

8. дизъюнкция – искомая логическая функция ($\overline{(A\vee B)\bigwedge \overline{C}}\vee \overline{(A\vee C)\bigwedge B}$).

Инструкция . При вводе с клавиатуры используйте следующие обозначения: Например, логическое выражение abc+ab~c+a~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 1 *Х 2 *Х 3 ∨ Х 1 x 2 Х 3 ∨ Х 1 Х 2 x 3 ∨ Х 1 Х 2 Х 3
  ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
  б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
  КНФ может быть получена из таблицы истинности по следующему алгоритму:
  1) выбираем наборы переменных для которых функция на выходе =0
  2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
  3) логически перемножаются полученные суммы.
  Fскнф=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
  КНФ называется совершенной , если все переменные имеют одинаковый ранг.

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

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

Операция НЕ - логическое отрицание (инверсия)

• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.

Операция ИЛИ - логическое сложение (дизъюнкция, объединение)

Операция И - логическое умножение (конъюнкция)

Операция «ЕСЛИ-ТО» - логическое следование (импликация)

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Приоритет логических операций

• Действия в скобках
• Инверсия
• Конъюнкция (&)
• Дизъюнкция (V), Исключающее ИЛИ (XOR), сумма по модулю 2
• Импликация (→)
• Эквивалентность (↔)

Совершенная дизъюнктивная нормальная форма

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все логические слагаемые формулы различны.
3. Ни одно логическое слагаемое не содержит переменную и её отрицание.
4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Совершенная конъюнктивная нормальная форма

1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все элементарные дизъюнкции различны.
3. Каждая элементарная дизъюнкция содержит переменную один раз.
4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.

1. Определить порядок действий.

2. Определить размерность таблицы истинности.

Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их тоже два).

4. Сформулировать ответ.
В последнем столбце один "0", соответствующий А, равному "1", и В, равному "0". Получается, что данная функция ложна тогда и только тогда, когда логическая переменная А истинна, а логическая переменная В ложна, что соответствует логической функции СЛЕДСТВИЕ.
Значит, данная функция равна логическому следствию переменных А и В: Если А, то В.

Составить таблицу истинности для логической функции:

2. Определить размерность таблицы истинности.

"Шапка" таблицы содержит две строки - номера действий и логические операции действий.
Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их пять).
Количестко строк в таблице равно двойке в степени, равной количеству логических переменных - в случае двух переменных получается 4 строки..
3. Поочередно заполнить столбики таблицы в соответствии с логической функцией данного столбца.


4. Сформулировать ответ.
В последнем столбце "1", соответствуют А равному В, а "0" - А неравному В. Получается, что данная функция истинна, когда А равно В и ложна, когда А не равно В, что соответствует логической функции ТОЖДЕСТВО.
Значит, данная функция равна логическому ТОЖДЕСТВУ переменных А и В: А тождественно В.