Методические рекомендации рассмотрены и одобрены кафедрой вм и по 13 февраля 2008 г., протокол №5 Рецензент Кацуба В. С., канд физ мат наук, доцент кафедры высшей математики и программного обеспечения (стр. 3 из 10)
Логические операции можно задавать при помощи таблиц истинности, показывающих соответствие значений истинности высказываний. Для высказываний x и
эта таблица имеет вид: | х |  |
| 1 | 0 |
| 0 | 1 |
Конъюнкцией двух высказываний х и y называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания х и y. Конъюнкция обозначается: х Ù y, или х & y (читается: «х и y»). Таблица истинности для х Ù y имеет вид:
| х | y | х Ù y |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
Дизъюнкцией двух высказываний х и y называется высказывание, ложное тогда и только тогда, когда оба высказывания х и y ложны. Дизъюнкция обозначается х Ú y (читается: «х или y»). Таблица истинности для х Ú y имеет вид:
| х | y | х Ú y |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Импликацией двух высказываний х и y называется высказывание, ложное тогда и только тогда, когда высказывание х истинно, а y – ложно. Импликация обозначается: х ® y (читается: «х влечет y» или «из х следует y»). Высказывание х называется посылкой импликации, а высказывание y – следствием. Таблица истинности для х ® y имеет вид:
| х | y | х ® y |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Эквиваленцией (эквивалентностью) двух высказываний х и y называется высказывание, истинное тогда и только тогда, когда истинности высказываний х и y совпадают. Эквиваленция обозначается: х « y, или х ~ y (читается: «х эквивалентно y» или «х тогда и только тогда, когда y»). Таблица истинности для х « y имеет вид:
| х | y | х « y |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
1.2. Формулы алгебры логики
Формулами алгебры логики называются выражения, полученные из переменных x, y,… посредством применения логических операций: отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции, а также сами переменные, принимающие значения истинности высказываний x, y,….
Формулы алгебры логики будем обозначать большими буквами латинского алфавита: А, В,…..
Если в формулу алгебры логики вместо переменных x, y,… подставить конкретные высказывания, то получится высказывание, имеющее логическое значение «1» или «0».
Пример.
Высказывание x: «Волга впадает в Каспийское море» – истинное (x = 1),
высказывание y: «Число 16 кратно 3» – ложное (y = 0),
тогда формула А = x Ú y будет иметь логическое значение «1»: А = 1 (см. таблицу истинности для х Ú y).
На основе таблиц истинности основных логических операций можно составлять таблицы истинности для различных формул алгебры логики.
Две формулы алгебры логики называются равносильными или эквивалентными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы переменных (элементарных высказываний). Равносильность формул А и В будем обозначать знаком «º»: А º В.
Равносильность логических формул можно установить при помощи их таблиц истинности.
Пример. С помощью таблиц истинности проверить, являются ли равносильными формулы А =
и В = 
.Решение. Составим таблицы истинности для каждой из формул А и В.
| x | y | |  | Ù | А =  |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| x | y | | x Ú y |  | В =  |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 |
Ответ: данные формулы являются равносильными.
Другой способ доказательства равносильности логических формул – их упрощение с использованием основных равносильностей.
Основные равносильности.
Для любых элементарных высказываний x, y, z справедливы следующие равносильности, которые можно разбить на 3 группы.
1. Основные законы:
1) x Ù x º x; 2) x Ú x º x; 3)
º x;4) x Ù 0 º 0; 5) x Ú 0 º x; 6)
Ù x º 0;7) x Ù 1 º x; 8) x Ú 1 º 1; 9)
Ú x º 1;законы поглощения:
10) x Ù (y Ú x) º x; 11) x Ú (y Ù x) º x.
2. Выражения одних логических операций через другие:
12) x ® y º
Ú y; 13) 
;14) x « y º (x ® y) Ù (y ® x); 15)
.3. Свойства логических операций:
16) x Ù y º y Ù x; 17) x Ú y º y Ú x;
18) x Ù (y Ù z) º (x Ù y) Ù z; 19) x Ú (y Ú z) º (x Ú y) Ú z;
20) x Ù (y Ú z) º (x Ù y) Ú (x Ù z); 21) x Ú (y Ù z) º (x Ú y) Ù (x Ú z).