Составление таблиц истинности. Составление функциональных схем по логическим формулам

Принцип работы переключателя настольной лампы таков: если лампа горела, переключатель выключает её, если лампа не горела – включает её. Такой переключатель можно считать электрическим аналогом операции отрицания.

В обыденной и научной  речи, кроме базовых логических связок «и», «или», «не» используются и некоторые  другие: «если …, то»,  «тогда и  только тогда, когда» и др.

Эти связки имеют в алгебре  логики также свои назначения и обозначения.

4. Логическое следование (импликация) – соединение двух высказываний в одно с помощью оборота речи «если … , то …»

Обозначения: А Þ В = А →  В

А	В	С=А Þ В
0	0	1
0	1	1
1	0	0
1	1	1

Логическое следование отличается от обычного понимания слова «следует».

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

Примеры:

1) Рассмотрим высказывание  «Если идет дождь, то на улице  сыро». Здесь исходные высказывания  «Идет дождь» и «На улице  сыро». Если не идет и не  сыро на улице, результат операции  следования – истина. На улице  может быть сыро и без дождя,  например, когда прошла поливочная машина или дождь прошел накануне. Результат операции ложен только, когда дождь идет, а на улице не сыро.

2) Рассмотрим два высказывания: А{х делится на 9}, В{х делится на 3}. Операция А®В означает следующее: «Если число делится на 9, то оно делится и на 3». Рассмотрим возможные варианты:

• А – ложно, В – ложно (1-я строка таблицы истинности). Можно найти такие числа, для которых истиной является условие «если А – ложно, то и В – ложно». Например, х = 4, 17, 22.
• А – ложно, В – истинно (2-я строка таблицы истинности). Можно найти такие числа, для которых истиной является условие «если А – ложно, то и В – истинно». Например, х = 6, 12, 21.
• А – истинно, В – ложно (3-я строка таблицы истинности). Невозможно найти такие числа, которые делились бы на 9, но не делились на 3. Истинная предпосылка не может приводить к ложному результату импликации.
• А – истинно, В – истинно (4-я строка таблицы истинности). Можно найти такие числа, для которых истиной является условие «если А – истинно, то и В – истинно». Например, х = 9, 18, 27.

5. Логическое равенство (эквивалентность) – соединение двух высказываний в одно с помощью оборота речи « … тогда и только тогда, когда …».

Обозначается: А ~ В или А  Û В или А = В или А º В.

Пример. Высказывания А = «2 + 2 = 7» и В = «1–8=5». Сложное высказывание  
А ≡ В (А ~ В) истинно, так как оба высказывания ложны.

 

А	В	С=А ÛВ
0	0	1
0	1	0
1	0	0
1	1	1

Примеры операции эквивалентности:

1) День сменяет ночь  тогда и только тогда, когда  солнце скрывается за горизонтом;

2) Добиться результата  в спорте можно тогда и только  тогда, когда приложено максимум  усилий.

 

6. Антиконъюнкция (штрих Шеффера) – это соединение двух высказываний в одно с помощью оборота речи неверно, что А и В.

Обозначение: А | В.

Результатом операции антиконъюнкции для высказывания А | В будет ложь только тогда, когда оба высказывания истинны.

А	В	С=А | В
0	0	1
0	1	1
1	0	1
1	1	0

Пример . Высказывания А= «Москва – столица России» и В= «Рим – столица Италии».

Сложное высказывание А | В ложно, так как истинны оба высказывания.

 

 

7. Антидизъюнкция (стрелка Пирса) – это соединение двух высказываний в одно с помощью оборота речи ни А, ни В.

Обозначение: А ¯ В и высказывание будет истинна только тогда, когда оба высказывания ложны.

А	В	С=А ¯ В
0	0	1
0	1	0
1	0	0
1	1	0

 

Пример . Высказывания А= «Рим – столица России» и В= «Москва – столица Италии». Сложное высказывание А ¯ В истинно, так как ложны оба высказывания.

 

 

8. Строгая дизъюнкция. Этой операции соответствует логическая связка «либо … либо»

Обозначение: А Å В.

А	В	С=А Å В
0	0	0
0	1	1
1	0	1
1	1	0

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

 

 

Операции импликация, эквивалентность, штрих Шеффера, стрелка Пирса и «сложение по модулю 2» могут быть сведены путем логических преобразований к трем базовым: И, ИЛИ,  НЕ.

Основными символами алгебры логики являются:

• Пропозициональные переменные;
• Унарные связки Ø или бинарные связки Ù, Ú, ®, Þ;
• Скобки ().

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

Далее индуктивно вводится понятие формулы, являющееся формализацией понятия «сложного» высказывания. К формуле алгебры логики относят:

• выражение, состоящее только из пропозициональной переменной (А1, В, с);
• выражения, состоящие из пропозициональных формул соединенных связками (¬ С, (А1∧ А2), (Н1 → Н2)).

Правила сокращения записей  в пропозициональных формулах:

• вместо ¬ А пишут ;
• вместо А1 ∧ А2 пишут А1А2;
• внешние скобки опускаются.

Примеры:

1) ;

2) .

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

1. действия в скобках;
2. инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность.

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

1. Для формулы (АÚВ)Ù(ùА ÚùВ) построить таблицу истинности.

Количество логических переменных 2, следовательно, количество строк  в таблице истинности  должно быть 2²=4.

Количество логических операций  в формуле 5, следовательно, количество столбцов в таблице истинности должно быть 2+5=7 (количество переменных плюс количество операций).

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

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

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

А	В	АÚВ	ùА	ùВ	ùАÚùВ	(АÚВ)Ù(ùА ÚùВ)
0	0	0	1	1	1	0
0	1	1	1	0	1	1
1	0	1	0	1	1	1
1	1	1	0	0	0	0

2. Для формулы АÙ(ВÚùВÙùС) построить таблицу истинности .

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

А	В	С			Ù	ВÚ( Ù )	АÙ(ВÚ Ù )
0	0	0	1	1	1	1	0
0	0	1	1	0	0	0	0
0	1	0	0	1	0	1	0
0	1	1	0	0	0	1	0
1	0	0	1	1	1	1	1
1	0	1	1	0	0	0	0
1	1	0	0	1	0	1	1
1	1	1	0	0	0	1	1

3. Составить таблицу истинности для данной формулы: .

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

x	y	z
0	0	0	1	0	0	1	0
0	0	1	0	0	0	1	1
0	1	0	1	0	0	1	0
0	1	1	0	0	1	0	1
1	0	0	0	0	0	1	1
1	0	1	1	0	0	1	0
1	1	0	0	1	0	0	1
1	1	1	1	1	1	1	0

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

Для описания того, как функционируют  аппаратные средства компьютера очень  удобен математический аппарат алгебры логики, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры «1» и «0».