Логическое умножение (конъюнкция или логическое И)
Определение. Конъюнкцией высказываний называют такое сложное высказывание Y, которое истинно только тогда, когда истинны все входящие в него простые высказывания.
Диаграмма Эйлера-Венна операции Иизображена на рис.3.2. Таблица истинности операции логического умножения имеет следующий вид:
| X | Y | X И Y |
| Нет (0) | Нет (0) | Нет (0) |
| Нет (0) | Да (1) | Нет (0) |
| Да (1) | Нет (0) | Нет (0) |
| Да (1) | Да (1) | Да (1) |
При записи конъюнкции применяют и такие обозначения: X И Y,X & Y или X Ù Y.
3.6.3.Логическое сложение (дизъюнкция или логическое ИЛИ)
Определение. Дизъюнкцией высказываний называется такое сложное высказывание Y, которое истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний.
Диаграмма Эйлера-Венна операции ИЛИизображена на рис.3.3. Таблица истинности операции логического сложения имеет следующий вид:
| X | Y | X ИЛИ Y |
| Нет (0) | Нет (0) | Нет (0) |
| Нет (0) | Да (1) | Да (1) |
| Да (1) | Нет (0) | Да (1) |
| Да (1) | Да (1) | Да (1) |
При записи дизъюнкции применяют также следующие обозначения: X ИЛИ Y, X + Y, X Ú Y.
Логические выражения.
С помощью основного набора булевых операций можно построить более сложные логические высказывания.
Пример: Построим логическое выражение из простых логических операций для описания сложного логического умозаключения «Я буду читать, если есть хорошая книга и есть свободное время или если я ищу ответ на интересующий меня вопрос и надеюсь найти его в этой книге».
Введем следующие обозначения:
Х1 — переменная, характеризующее фактор «есть хорошая книга», 1 – есть, 0 – нет;
Х2 — переменная, определяющая условие «есть свободное время», 1 – есть, 0 – нет;
Х3 — параметр «ищу ответ на вопрос», 1 – да (ищу), 0 –нет (не ищу);
Х4 — фактор «надеюсь найти ответ», 1 – да (надеюсь), 0 – нет (не надеюсь);
Ф(Х1, Х2, Х3, Х4)— логическое выражение, описывающее приведенное высказывание.
Тогда сложная функция, определяющая условие, при котором я буду читать, может быть записывается с помощью логического выражения:
Ф(Х1, Х2, Х3, Х4)=(Х1 И X2) ИЛИ (X3 И X4),
при этом таблица истинности такого выражения имеет вид:
Таблица. 3.2.
| X1 | X2 | X3 | X4 | Ф(Х1, Х2, Х3, Х4) |
| Нет (0) | Нет (0) | Нет (0) | Нет (0) | Нет (0) |
| Да (1) | Нет (0) | Нет (0) | Нет (0) | Нет (0) |
| Нет (0) | Да (1) | Нет (0) | Нет (0) | Нет (0) |
| Нет (0) | Нет (0) | Да (1) | Нет (0) | Нет (0) |
| Нет (0) | Нет (0) | Нет (0) | Да (1) | Нет (0) |
| Да (1) | Да (1) | Нет (0) | Нет (0) | Да (1) |
| Да (1) | Нет (0) | Да (1) | Нет (0) | Нет (0) |
| Да (1) | Нет (0) | Нет (0) | Да (1) | Нет (0) |
| Нет (0) | Да (1) | Да (1) | Нет (0) | Нет (0) |
| Нет (0) | Да (1) | Нет (0) | Да (1) | Нет (0) |
| Нет (0) | Нет (0) | Да (1) | Да (1) | Да (1) |
| Да (1) | Да (1) | Да (1) | Нет (0) | Да (1) |
| Да (1) | Да (1) | Нет (0) | Да (1) | Да (1) |
| Да (1) | Нет (0) | Да (1) | Да (1) | Да (1) |
| Нет (0) | Да (1) | Да (1) | Да (1) | Да (1) |
| Да (1) | Да (1) | Да (1) | Да (1) | Да (1) |
Утверждение. В булевой алгебре существуют определенные взаимоотношения между логическими функциямиИ, ИЛИ, НЕ, которые позволяют производить замену функций ИфункциейИЛИи наоборот. Это взаимоотношения известны как теоремы де Моргана:
НЕ (X1 И X2)= [НЕ (X1)] ИЛИ [НЕ (X2)]
НЕ (X1 ИЛИ X2)= [НЕ (X1)] И [НЕ (X2)]
В булевой алгебре выведены ряд определений и правил, которые необходимы для анализа и синтеза логических схем, используемых в вычислительной технике.
Вот эти наиболее важные теоремы булевой алгебры [12]):
Таблица. 3.3.
| 1а `0 = 1 | 1б `1 = 0 |
| 2а Х Ú 0 = Х | 2б Х & 1= Х |
| 3а Х Ú 1 = 1 | 3б Х & 0 = 0 |
| 4а Х Ú Х = Х | 4б Х & Х = Х |
| 5а Х Ú`Х = 1 | 5б Х &`Х = 0 |
| 6а Х1 Ú Х2 = Х2 Ú Х1 | 6б Х1 & Х2 = Х2 & Х1 |
| 7а Х1 Ú (Х1 & Х2) = Х1 | 7б Х1 & (Х1 Ú Х2) = Х1 |
| 8а Х1 Ú (`Х1 & Х2) = Х1 Ú Х2 | 8б Х1 & (`Х1 Ú Х2) = Х1 & Х2 |
| 9а (Х1 Ú Х2) Ú Х3 = Х1 Ú (Х2 Ú Х3) | 9б (Х1 & Х2) & Х3= Х1 & (Х2 & Х3) |
| 10а Х1 Ú (Х2 & Х3) = (Х1 Ú Х2) & (Х1 Ú Х3) | 10б Х1 & (Х2 Ú Х3)=(Х1 & Х2) Ú (Х1 & Х3) |
Утверждение. С помощью приведенных соотношений можно получать так называемые эквивалентные выражения, которые могут оказаться существенно проще, чем исходное логические выражения.
Пример: Пусть имеется следующее логическое выражение
(X1 Ú X2) & ( X1 Ú`X2) Ú X3 .
Учитывая теорему 10а, получим
(X1 Ú X2) & ( X1 Ú`X2) Ú X3 = (X1 Ú X2 &`X2) Ú X3.
Далее по теореме 5а имеемX2 &`X2= 0, тогда
(X1 Ú X2) & ( X1 Ú`X2) Ú X3 =X1 Ú 0 Ú X3,
а по теореме 2а X1 Ú 0 = X1и
(X1 Ú X2) & ( X1 Ú`X2) Ú X3 =X1 Ú X3.
Утверждение. По некоторому наперед заданному булевому выражению можно легко построить его таблицу истинности. Для этого в выражение подставляют вместо переменных их возможные значения и вычисляют значение выражения.
Примечание.
Количество состояний логической функции (или строк), которые должны быть отражены в таблице истинности определяется по формуле 2n , где n — количество логических переменных.
Пример: Пусть необходимо построить таблицу истинности для выражения
Ф(Х1, Х2)=(`X1 & X2) Ú (X1 &`X2)
Поскольку Ф(Х1, Х2)является функцией от двух переменных, то таблица истинности должна содержать 22=4 строки. Таблица истинности рассматриваемого логического выражения имеет следующий вид:
| Х1 | X2 | `X1 | `X2 | `X1 & X2 | X1 &`X2 | Ф(Х1, Х2) |