Все реки впадают в море
Все школьники - отличники
Все книги имеют страницы
Все планеты вращаются вокруг звезд
Сократ - человек.
Следовательно, Сократ смертен."
Под высказыванием (суждением) будем понимать повествовательное предложение, относительно которого можно сказать, истинно оно или ложно.
Обозначать высказывания будем большими буквами. Если высказывание А истинное, то будем писать "А = 1" и говорить: "А - истинно". Если высказывание Х ложно, то будем писать "Х = 0" и говорить "Х ложно".
ПРИМЕРЫ
1. ЛОГИЧЕСКОЕ ОТРИЦАНИЕ (ИНВЕРСИЯ)
Образуется из простого высказывания с помощью добавления частицы НЕ к сказуемому или использованием оборота речи "НЕВЕРНО, ЧТО ...".
|
А |
Значение А |
инверсия А |
Значение не А |
|
У меня есть приставка "DENDY" |
0 |
У меня нет приставки "DENDY" |
1 |
|
Я не знаю китайский язык |
1 |
Неверно, что я не знаю китайский язык (я знаю китайский язык) |
0 |
Инверсия обозначается : не А; ¬А; not A
Нас интересует значение истинности высказывания формы не А (а не его содержание). Определяется оно по специальной таблице истинности, которая для операции инверсии выглядит так:
|
А |
|
Читается |
|
0 |
1 |
если А ложно, то не А истинно |
|
1 |
0 |
если А истинно, но не А ложно |
Мнемоническое правило: слово инверсия (от лат. inversio - переворачивание) означает, что белое меняется на черное, добро на зло, красивое на безобразное, истина на ложь, ложь на истину, ноль на один, один на ноль.
Примечание 1. Логики предпочитают иметь дело с выражениями неверно, что, поскольку тем самым подчеркивается отрицание всего высказывания.
Примечание 2. Дважды или четырежды отрицавшееся высказывание имеет то же самое значение истинности, что и соответствующие не отрицавшееся высказывание, трижды отрицавшееся что и отрицавшееся один раз.
ЛОГИЧЕСКОЕ УМНОЖЕНИЕ (КОНЪЮНКЦИЯ)
Образуется соединением двух высказываний в одно с помощью союза "И".
ПРИМЕРЫ: Допустим, из моего окна видна автостоянка, на которой обычно стоят две машины: Мерседес и Жигули, но может находиться и какая-то одна из них, или не быть ни одной. Обозначим высказывания:
А = На автостоянке стоит "Мерседес"
В = На автостоянке стоят "Жигули"
А конъюнкция В = На автостоянке стоят "Мерседес" и "Жигули"
Операция конъюнкции обозначается: Λ; &; *; and; и.
|
А |
B |
A L B |
Пояснение |
Стоят Мерседес и Жигули |
|
0 |
0 |
0 |
Мерседес не стоит, Жигули не стоят |
ЛОЖЬ |
|
0 |
1 |
0 |
Мерседес не стоит, Жигули стоят |
ЛОЖЬ |
|
1 |
0 |
0 |
Мерседес стоит, Жигули не стоят |
ЛОЖЬ |
|
1 |
1 |
1 |
Мерседес стоит, Жигули стоят |
ИСТИНА |
Из таблицы истинности следует, что операция конъюнкции истинна тогда и только тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно высказывание ложно. Иногда это свойство принимают за определение операции логического умножения.
Мнемоническое правило: конъюнкция - это логическое умножение, и мы не сомневаемся, что Вы заметили:
0 х 0 = 0,
0 х 1= 0,
1 х 0 = 0,
1 х 1 = 1.
|
Таблица истинности
|
Пересечение множеств
|
А - множество отличников в классе |
ЛОГИЧЕСКОЕ СЛОЖЕНИЕ (ДИЗЪЮНКЦИЯ)
Образуется соединением двух высказываний в одно с помощью союза ИЛИ.
Примеры
Завтра дождь будет или не будет (третьего не дано).
Петя сидит на западной или восточной трибуне стадиона.
Студент едет в электричке или читает книгу.
Обозначается:
А или В; А OR В; А | В; А V В
ПРИМЕРЫ: Допустим, из моего окна видна автостоянка, на которой обычно стоят две машины: Мерседес и Жигули, но может находиться и какая-то одна из них, или не быть ни одной. Обозначим высказывания:
А = На автостоянке стоит "Мерседес"
В = На автостоянке стоят "Жигули"
А дизъюнкция В = На автостоянке стоят "Мерседес" или "Жигули"
|
А |
B |
A V B |
Пояснение |
Стоят Мерседес или Жигули |
|
0 |
0 |
0 |
Мерседес не стоит, Жигули не стоят |
ЛОЖЬ |
|
0 |
1 |
1 |
Мерседес не стоит, Жигули стоят |
ИСТИНА |
|
1 |
0 |
1 |
Мерседес стоит, Жигули не стоят |
ИСТИНА |
|
1 |
1 |
1 |
Мерседес стоит, Жигули стоят |
ИСТИНА |
Из таблицы истинности следует, что операция дизъюнкции ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно высказывание истинно. Иногда это свойство принимают за определение операции логического умножения.
Мнемоническое правило: дизъюнкция - это логическое сложение, и мы не сомневаемся, что Вы заметили:
0 + 0 = 0,
0 + 1= 1,
1 + 0 = 1,
но в логике: 1 V 1 = 1.
|
Таблица истинности
|
Объединение множеств
|
А - множество отличников в классе |
ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ (ИМПЛИКАЦИЯ)
Образуется соединением двух высказываний в одно с помощью оборота речи "ЕСЛИ ..., ТО... "
ПРИМЕРЫ
Если клятва дана, то она должна выполняться.
Если число делится на 9, то оно делится на 3.
Исторически операция импликации была введена для полноты системы логических функций двух переменных, поэтому в логике допустимо (принято, договорились) рассматривать и бессмысленные с житейской точки зрения высказывания. Приведем примеры, которые не только правомерно рассматривать в логике, но при этом значение их истинно.
Если коровы летают, то 2 + 2 = 5
Если я - Наполеон, то у кошки четыре ноги.
Импликация обозначается: А В;
Говорят: "Если А, то В", "А имплицирует В", "А влечет В", "В следует из А".
|
А |
B |
A ή B |
Пояснение |
Если идет дождь, то асфальт мокрый |
|
0 |
0 |
1 |
дождя нет, асфальт сухой |
ИСТИНА |
|
0 |
1 |
1 |
дождя нет, асфальт мокрый |
ИСТИНА |
|
1 |
0 |
0 |
дождь идёт, асфальт сухой |
ЛОЖЬ |
|
1 |
1 |
1 |
дождь идёт, асфальт мокрый |
ИСТИНА |
Из таблицы истинности видно, что импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания следует ложное (истинная предпосылка ведет к ложному выводу). Иногда это свойство принимают за определение операции импликации.
ЛОГИЧЕСКОЕ РАВЕНСТВО (ЭКВИВАЛЕНТНОСТЬ)
Образуется соединением двух высказываний в одно при помощи оборота речи "... ТОГДА И ТОЛЬКО ТОГДА, КОГДА ...".
ПРИМЕРЫ
Угол называется прямым тогда и только тогда, когда он равен 90 градусов
Две прямые параллельны тогда и только тогда, когда они не пересекаются
Любая материальная точка сохраняет состояние покоя или равномерного прямолинейного движения тогда и только тогда, когда внешнее воздействие не изменит этого состояния (Первый закон Ньютона).
Голова думает тогда и только тогда, когда язык отдыхает (Шутка)
Все законы математики, физики, все определения - суть эквивалентность высказываний.
Эквивалентность обозначается: А = В; А ~ В
ПРИМЕР. Пусть даны два высказывания:
А = Число делится на 3 без остатка (кратно трём)
В = Сумма цифр числа делится нацело на 3".
А эквивалентно В = "Число делится на 3 без остатка тогда и только тогда, когда сумма цифр данного числа делится нацело на 3".
|
А |
B |
A Ϋ B |
Пояснение |
Число кратно трём тогда и только тогда, когда сумма цифр кратна трём |
|
0 |
0 |
1 |
число не кратно трём, сумма цифр не кратна трём |
ИСТИНА |
|
0 |
1 |
0 |
число не кратно трём, сумма цифр кратна трём |
ЛОЖЬ |
|
1 |
0 |
0 |
число кратно трём, сумма цифр не кратна трём |
ЛОЖЬ |
|
1 |
1 |
1 |
число кратно трём, сумма цифр кратна трём |
ИСТИНА |
Из таблицы истинности следует, что эквивалентность двух высказываний истинна, тогда и только тогда, когда оба эти высказывания истинны, или оба ложны. Иногда это свойство принимается за определение операции эквивалентности.
В формулах алгебры логики используются только логические переменные. Логические связки (И, ИЛИ) обозначают логические операции. Каждая формула задает логическую функцию, которая сама может принимать только одно из двух логических значений (0 или 1). То есть вместо выражения Е = А V В можно написать F(A,B) = A V B и рассматривать его как функцию двух переменных.
Мы рассмотрели основные логические операции двух переменных. Сколько же всего может быть различных логических (т.е. двузначных) функций от двух переменных? Попробуем ответить на этот вопрос.
Две переменные, каждая из которых может быть либо нулём, либо единицей, образуют 22 = 4 различных набора значений: (0,0); (0,1); (1,0); (1,1). Для каждого набора сама функция может принять значение либо 0, либо 1. Например, F(0,0)=1; F(0,1)=1; F(1,0)=0; F(1,1)=0. Тогда всего различных функций двух переменных будет шестнадцать (42=16).
Из таблицы видно, что каждой функции соответствует её отрицание (константа 1 - отрицание константы 0).
Функцию можно задавать как в виде формулы, так и в табличном виде. Переход от табличного задания к булевой формуле всегда возможен.
Сводная таблица логических функций двух переменных
|
Значение Х |
0 |
0 |
1 |
1 |
|
|
|
Значение Y |
0 |
1 |
0 |
1 |
||
|
|
Значение функции |
Название функции |
Обозначение функции |
|||
|
Функция 0 |
0 |
0 |
0 |
0 |
константа 0 |
F = 0 |
|
Функция 1 |
0 |
0 |
0 |
1 |
конъюнкция |
F = X L Y |
|
Функция 2 |
0 |
0 |
1 |
0 |
отрицание импликации XY |
F= Ψ(X ή Y) |
|
Функция 3 |
0 |
0 |
1 |
1 |
переменная Х |
F = X |
|
Функция 4 |
0 |
1 |
0 |
0 |
отрицание импликации YX |
F= Ψ(Y ή X) |
|
Функция 5 |
0 |
1 |
0 |
1 |
переменная Y |
F = Y |
|
Функция 6 |
0 |
1 |
1 |
0 |
отрицание эквивалентности |
F= Ψ(X Ϋ Y) |
|
Функция 7 |
0 |
1 |
1 |
1 |
дизъюнкция |
F= X V Y |
|
Функция 8 |
1 |
0 |
0 |
0 |
отрицание дизъюнкции |
F= Ψ(X V Y) |
|
Функция 9 |
1 |
0 |
0 |
1 |
эквивалентность |
F = X Ϋ Y |
|
Функция 10 |
1 |
0 |
1 |
0 |
отрицание Y |
F = ΨY |
|
Функция 11 |
1 |
0 |
1 |
1 |
импликация YX |
F = Y ή X |
|
Функция 12 |
1 |
1 |
0 |
0 |
отрицание Х |
F = ΨX |
|
Функция 13 |
1 |
1 |
0 |
1 |
импликация XY |
F = X ή Y |
|
Функция 14 |
1 |
1 |
1 |
0 |
отрицание конъюнкции |
F = Ψ(X L Y) |
|
Функция 15 |
1 |
1 |
1 |
1 |
константа 1 |
F = 1 |
СЛОЖНОЕ ВЫСКАЗЫВАНИЕ
Если несколько простых высказываний объединены в одно с помощью логических операций, то такое высказывание называется сложным.
|
Сложное высказывание |
Составляющие простые высказывания |
Форма сложного высказывания |
|
Е = Идёт дождь, а у меня нет зонта |
А=Идёт дождь |
Е = А L ΨВ |
|
Е = Когда живётся весело, то и работа спорится |
А = Живётся весело |
Е = А ή В |
|
Е = Идёт налево - песнь заводит, направо - сказку говорит |
А = Идёт налево |
E=(A ή C)V(B ή D) |
Мы всегда исходим из того, что для любого простого высказывания определено (известно), является ли оно истинным или ложным. По форме сложного высказывания и по таблицам истинности входящих в него логических операций всегда можно определить, истинное оно или ложное.
Реальную задачу, как правило, мы получаем в виде текста на естественном языке. И прежде, чем приступить к ее решению, мы должны выделить простые высказывания, отношения (связи) между ними и перевести их на язык формул (формализовать условие задачи, определить форму). Разберём примеры формализации сложных высказываний.
Определить форму сложного высказывания
Пример 1. Е = " Ваш приезд не является ни необходимым, ни желательным"
Составляющие высказывания:
А = " Ваш приезд необходим ";
В = " Ваш приезд желателен "
Ответ: E= не(A) & не(B)
Пример 2. Е = " Поиски врага длились уже три часа, но результатов не было, притаившийся враг ничем себя не выдавал"
Составляющие высказывания:
А = "Поиски врага длились три часа"
В = "Врага нашли (результат есть)"
С = "Враг себя выдал".
Ответ: E= не(C) → A & не(B)
Пример 3. E = " Если вчера было пасмурно, то сегодня ярко светит солнце"
А = "Вчера было пасмурно";
В = "Сегодня ярко светит солнце"
Ответ: Е = А → B
Вычисление значений логических выражений выполняется в определенном порядке, согласно их приоритету:
- инверсия
- конъюнкция
- дизъюнкция
- импликация и эквивалентность
Операции одного приоритета выполняются слева направо. Для изменения порядка дейcтвий используются скобки.
ПРИМЕР 1: А V (B → C) & D = не(A)
Порядок выполнения:
Не(А) - инверсия
В → С - импликация
(В → С) & D - конъюнкция
А V (B → C) & D - дизъюнкция
А V (B → C) & D = не(A)- эквивалентность
Построим таблицу истинности для высказывания
E = (A V не(B)) → не(C)
В высказывание Е входят три переменные: А, В, С (n=3 ) и четыре логические операции: инверсия В, инверсия С, дизъюнкция, импликация.
Таблица истинности будет состоять из 23 + 2 (заголовок) = 8 +2 = 10 строк и 3 + 4 = 7 столбцов
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| A | B | С | не(В) | не(С) | А v не(В) | А v не(В)→не(С) |
| 0 | 0 | 0 | ||||
| 0 | 0 | 1 | ||||
| 0 | 1 | 0 | ||||
| 0 | 1 | 1 | ||||
| 1 | 0 | 0 | ||||
| 1 | 0 | 1 | ||||
| 1 | 1 | 0 | ||||
| 1 | 1 | 1 |
Если сложное высказывание истинно для всех значений входящих в него переменных, то такое высказывание называется ТОЖДЕСТВЕННО ИСТИННЫМ или тавтологией (обозначается константой 1).
НАПРИМЕР высказывание: "Демократ - это человек, исповедующий демократические убеждения" - всегда истинно, то есть является тавтологией.
Все математические, физические и др. законы являются тавтологиями. Например: (а+b)2 = a2 + 2ab + b2
Прогноз погоды на завтра может быть, например, таким: "Дождь будет или дождя не будет". Такое предсказание будет всегда истинным, хотя вряд ли кого устроит. Его математическая запись:
А V не(А) = 1
(по закону исключенного третьего всегда должно быть истинным либо суждение, либо его отрицание).
Проверить, является ли сложное высказывание тождественно истинным, можно по таблице истинности.
Если сложное высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется ТОЖДЕСТВЕННО ЛОЖНЫМ (обозначается константой 0 ).
НАПРИМЕР, высказывание: "Сегодня среда, а это - второй день недели" является тождественно ложным. Тождественно ложным является и следующее высказывание: "Компьютер включен и компьютер не включен (выключен)". Математическая запись его такова:
A & не(A) = 0
(по закону противоречия: не могут быть одновременно истинны утверждение и его отрицание.)
Если значения сложных высказываний совпадают при всех возможных значениях входящих в них переменных, то такие высказывания называют РАВНОСИЛЬНЫМИ, ТОЖДЕСТВЕННЫМИ, ЭКВИВАЛЕНТНЫМИ
Упрощение сложных высказываний - это замена высказывания на равносильное ему на основе законов алгебры высказываний
При решении логических задач часто приходится упрощать формулы. Упрощение формул в булевой алгебре производится на основе эквивалентных преобразований, опирающихся на основные законы.
Законы логики высказываний - это такие выражения, которым всегда соответствует истинное высказывание, какие бы подстановки значений мы ни делали вместо переменных. В алгебре высказываний логические законы выражаются в виде формул.
1.1. Закон тождества:
А = А
- всякая мысль тождественна самой себе, то есть "А есть А", где А любое высказывание.
2. Закон исключенного третьего:
А V ¬А = 1
- в один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо А, либо не А.
НАПРИМЕР. "Число 123 либо четное, либо нечетное, третьего не дано".
Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: либо-либо, истина-ложь. Там же где встречается неопределенность (например, в рассуждениях о будущем), закон исключенного третьего часто не может быть применен.
Рассмотрим следующее высказывание: "Это предложение ложно". Оно не может быть истинным, потому, что оно утверждает, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным. Это высказывание не истинно и не ложно, а потому нарушается закон исключенного третьего.
Парадокс (греч. paradoxos - неожиданный, странный) возникает из-за того, что предложение ссылается само на себя. Другим известным парадоксом является задача о парикмахере:
"В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы парикмахеру?"
В нашей формальной системе нет возможности ввести такое ссылающееся само на себя истолкование, поэтому мы не можем выразить все возможные мысли и доводы.
3. Закон непротиворечия:
¬(¬ А ^ А) = 1
- не могут быть одновременно истинными суждение и его отрицание. То есть, если высказывание А - истинно, то его отрицание ¬А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным.
3a. А ^ ¬А =0.
Именно эта формула часто используется при упрощении сложных логических выражений.
Иногда этот закон формулируется так: два противоречащих друг другу высказывания не могут быть одновременно истинными.
ПРИМЕР. Е = "На Марсе есть жизнь и на Марсе жизни нет"
4. Закон двойного отрицания:
¬ ¬А = А
- если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание.
НАПРИМЕР: А = "Неверно, что Матроскин не кот"
эквивалентно высказыванию А = "Матроскин - кот".
СВОЙСТВА КОНСТАНТ
5. ¬0 = 1
6. ¬ 1 = 0
7. А V 0 = А
8. А ^ 0 = 0
9. А V 1 = 1
10. А ^ 1 = А
ЗАКОНЫ ИДЕМПОТЕНТНОСТИ
11. А V А = А
Отсутствие коэффициентов
12. А ^ А = А
Отсутствие степеней
12. А ^ А = А
Отсутствие степеней
Сколько бы раз мы ни повторяли "на улице тепло и на улице тепло" ни на один градус теплее от этого не станет, аналогично, от повторения телевизор включен или телевизор включен значение высказывания не меняется.
Сколько бы раз мы ни повторяли "на улице тепло и на улице тепло" ни на один градус теплее от этого не станет, аналогично, от повторения телевизор включен или телевизор включен значение высказывания не меняется.
ЗАКОНЫ КОММУТАТИВНОСТИ
13. А V В = В V А
14. А ^ В = В ^ А
ЗАКОНЫ АССОЦИАТИВНОСТИ
15. А V (В V С) = (А V В) V С
16. А ^ (В ^ С) = (А ^ В) ^ С
ЗАКОНЫ ДИСТРИБУТИВНОСТИ
17. А V (В^С) = (АVВ) ^ (АVС)
дизъюнкции относительно конъюнкции
18. А ^ (ВVС) = (А ^ В) V (А ^ С)
конъюнкции относительно дизъюнкции
Закон 18 аналогичен дистрибутивному закону в алгебре, а закон 17 аналога не имеет, он справедлив только в логике. Доказательство его удобнее всего провести по таблице истинности.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
А |
B |
C |
2 L 3 |
1 V 4 |
1 V 2 |
1 V 3 |
6 L 7 |
5 = 8 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
ЗАКОНЫ ПОГЛОЩЕНИЯ
19. А V А ^ В = А
20. А ^(А V В) = А
ЗАКОНЫ де МОРГАНА
21. ¬(А V В) = ¬ А ^¬ В
Отрицание вариантов
22. ¬(А ^ В) = ¬А V ¬В
Отрицание одновременной истинности
Мнемоническое правило. В левой части тождества операция отрицания стоит над всем высказыванием. В правой части она как бы разрывается и отрицание стоит над каждым из простых высказываний, но одновременно меняется операция дизъюнкция на конъюнкцию и наоборот.
ПРИМЕРЫ:
"Неверно, что я знаю арабский или китайский язык" тождественно тому, что "Я не знаю арабского языка и не знаю китайского языка"
"Неверно, что я выучил урок и получил по нему двойку" тождественно тому, что "или я не выучил урок, или я не получил двойку"
Операций импликации и эквивалентности иногда нет среди логических операций конкретного компьютера или транслятора с языка, а при решении задач они требуются. Существуют формулы замены данных операций с использованием только операций отрицания, дизъюнкции и конъюнкции. Так, вместо операции импликации можно использовать следующее тождественное выражение:
A → B = ¬A V B
Для замены операции эквивалентности существует два выражения:
A <=> B = (A ^ B) V (¬A ^ ¬B)
A <=> B = (A V ¬B) ^ (¬A V B)
Знание данных формул помогает, например, правильно построить отрицание импликации.
Рассмотрим следующий пример.
Пусть дано высказывание:
Е = "Неверно, что если я выиграю конкурс, то получу приз"
Пусть А = "Я выиграю конкурс", В = " Я получу приз", тогда
Е = ¬(A → B) = ¬(¬A V B) = ¬¬A ^ ¬B = A ^ ¬B,
то есть Е = "Возможно, что я выиграю конкурс, но приз не получу".
Интерес представляют и следующие формулы:
А → B = ¬B → ¬A
A <=> B = (A → B) ^ (B → A)
Доказать их справедливость можно также с помощью таблиц истинности. Интересно их выражение в разговорном языке. Например, фраза "Если Винни-Пух съел мед, то он сыт" тождественна фразе "Если Винни-Пух не сыт, то меда он не ел".
Для того, чтобы использовать какие-либо законы в практике, необходимо быть уверенным в их правильности. Доказать закон алгебры высказываний можно:
построив таблицу истинности для правой и левой части закона;
выполнив эквивалентные преобразования над правой и левой частью формулы для приведения их к одному виду;
с помощью диаграмм Эйлера-Венна;
путем правильных логических рассуждений.
Упрощение сложных высказываний - это замена их на равносильные им на основе законов алгебры высказываний.
При упрощении сложных высказываний используются следующие основные приемы:
по свойству констант
X = Х ^ 1, Х = X V 0
по закону исключенного третьего
1= A V ¬A
по закону противоречия
Z ^ ¬Z = 0
по закону идемпотентности
В = В V В = B V B V B V B,
C = C ^ C = C ^ C ^ C ^ C
по закону двойного отрицания
Е = ¬ ¬Е
Пример 1. Упростить: А ^В V А ^ ¬В
По закону дистрибутивности вынесем А за скобки:
А ^В V А ^ ¬В = A ^ (B V ¬B) = А ^ 1= А
Пример 2. (первый способ)
Упростить: (А V В) ^ (А V ¬В)
Раскроем скобки по закону дистрибутивности:
(А V В) ^ (А V ¬В) = A V (B ^ ¬B) =A V 0 = А
Пример 2. (второй способ)
Упростить: (А V В) ^ (А V ¬В)
Перемножим скобки (как в обычной алгебре) на основании того же закона дистрибутивности:
(А V В) ^ (А V ¬В) =
=A ^ A V A ^ ¬B V B ^ A V ¬B ^ B =
= A V A ^ (¬B V B) V 0 = = A V A ^ 1 = А
Пример 3.
Упростить: X V ¬X ^ Y
На первый взгляд, пример не позволяет его упростить, так как в этом выражении ничего нельзя вынести за скобки. Заметим, что хочется, чтобы у переменной Х появился Y. Для этого представим
Х как Х ^1, а 1 распишем по закону исключенного третьего
как (Y V ¬Y).
Далее раскроем скобки.
X ^(Y V¬Y) V ¬X ^ Y =
=X ^ Y V X ^ ¬Y V ¬X ^ Y =
добавим к полученному выражению X ^ Y.
Получим:
=X ^ Y V X ^ ¬Y V ¬X ^ Y V X ^ Y =
=X ^ (Y V ¬Y) V Y ^ (¬X V X) =
=X ^ 1 V Y ^ 1 =
=X V Y
Пример 4.
Упростить: A ^ C V B ^ ¬C V A ^ B
Один из возможных вариантов упрощения состоит в том, чтобы добавить к последнему слагаемому переменную С. Это делается стандартным способом: умножить А ^ B на 1, а 1 расписать как (С V ¬C).
A ^ C V B ^ ¬C V A ^ B ^ 1=
A ^ C V B ^ ¬C V A ^ B ^ (C V ¬C) =
A ^ C V B ^ ¬C V A ^ B ^ C V B ^ ¬C) =
A ^ C V B ^ ¬C V A ^ B ^ C V A ^ B ^ ¬C =
A ^ C ^ (1 V B) V B ^ ¬C ^ (1 V A) =
A ^ C ^ 1 V B ^ ¬C ^ 1 =
A ^ C V B ^ ¬C
Пример 5.
Упростить: ¬ (¬ X V ¬Y)
¬ (¬ X V ¬Y) =
применим закон де Моргана
¬¬ X ^ ¬¬ Y = X ^ Y= X ^ Y
Ценность теории определяется тем, насколько она применима на практике. Создание компьютеров стало возможным только тогда, когда нашли общую точку пересечения, совместились различные теоретические положения:
1673 год. Готфрид Вильгельм Лейбниц выдвинул идею применения в логике математической символики, предложил использовать двоичную систему счисления для целей вычислительной математики;
1848 год. Джордж Буль заложил основы булевой алгебры, поставив в соответствие 1 и 0 истинное и ложное значение;
1890 год. Герман Холлерита создал счетно-аналитическую машину, в которой впервые для расчетов использовано электричество и перфокарты;
1938 год. Алан Мэтисон Тьюринг разработал теорию логических автоматов и доказал, что универсальная вычислительная машина теоретически возможна и ей по силам решение практически неограниченного числа различных задач;
1945 год. Джон фон Нейман сформулировал основные принципы архитектуры ЭВМ, в которых обосновал использование двоичной системы счисления для представления информации в вычислительных машинах.
Рассмотрим, как применяется алгебра высказываний при конструировании устройств.
ЗАДАЧА 1. Пусть в некотором конкурсе решается вопрос о допуске того или иного участника к следующему туру тремя членами жюри P, Q, R. Решение положительно тогда и только тогда, когда хотя бы двое членов жюри высказались за допуск, причем среди них обязательно должен быть председатель жюри Q. Необходимо разработать устройство для голосования. Каждый член жюри нажимает на одну из двух кнопок (за или против), результат голосования всех трёх членов жюри определяется по тому, загорится (решение принято) или нет (решение не принято) сигнальная лампочка.
Формально это можно выразить так: требуется составить функциональную схему устройства, которое на выходе выдавало бы 1, если участник допускается к следующему туру, и 0, если не допускается.
Работу жюри можно легко представить в виде таблицы:
|
P |
Q |
R |
F(p,q,r) |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
Чтобы построить устройство мы хотим знать:
- каким образом следует реализовать логические значения 0 и 1 в электрические сигналы на входе и выходе устройства;
- каким образом описать работу этого устройства: формулой, схемой, таблицей истинности;
- существует ли алгоритм, позволяющий по известной таблице истинности построить схему устройства;
- из каких элементов должно состоять устройство.
Постановка подобных вопросов и поиск ответов на них привели к построению простейших преобразователей информации, составляющих основу любой вычислительной машины.
Всякое устройство ЭВМ, выполняющее арифметические действия над двоичными числами, можно рассматривать как функциональный преобразователь. Входными переменными (аргументами) его являются исходные двоичные числа, а выходной функцией от них - новое двоичное число, которое образовалось в результате выполнения данной операции. При этом как входные переменные, так и выходные функции могут принимать лишь одно из двух возможных значений - 0 (ложь) и 1 (истина).
Преобразователи, которые могут, получая сигналы об истинности отдельных простых высказываний, обработать их и в результате выдать значение логического отрицания, логической суммы или логического произведения, называются логическими элементами.
Цифровой сигнал - это сигнал, который может принимать только два установленных значения. Физическая природа сигнала может быть самой различной, например, появление на выходе схемы напряжения или силы тока определенной величины, включение лампы или звонка, нажатие кнопки, срабатывание электромагнитного реле и другие изменения в электрической цепи. При этом существенно, чтобы имелось два резко отличных состояния физических величин, моделирующих истинность или ложность логических высказываний.
Например:
есть два уровня напряжения: +5В и +0,4В
сила тока равна 20 мА и 1 мА
лампа горит или нет
кнопка нажата или нет и т.п.
В большинстве схем принято, что появление на выходе электрической цепи напряжения в пределах от 2,4В до 5В соответствует появлению единичного сигнала (высокий уровень цифрового сигнала), если же напряжения не превышает 0,5В, то сигнал принимают равным 0 (низкий уровень цифрового сигнала). Уровни напряжений между 0,5В и 2,4В считаются неопределенными.
Дальше, чтобы показать на схеме логический элемент, мы будем использовать стандартное условное обозначение. Это стандартное обозначение применяется независимо от того, на чем собран логический элемент: на реле, переключателях, пневматических устройствах, отдельных диодах или интегральных схемах.
ЛОГИЧЕСКИЙ ЭЛЕМЕНТ "НЕ" (инвертор).
Обеспечивает на выходе сигнал, противоположный сигналу на входе, т.е. на его выходе будет 1, если на вход поступает 0 и наоборот.
На схемах инверсия обозначается кружочком на выходе.
ЛОГИЧЕСКИЙ ЭЛЕМЕНТ "И"
(конъюнктор)
Логическим элементом "И" называется такой элемент, который на выходе выдает значение логического произведения входных сигналов.
На выходе элемент "И" дает 1 тогда и только тогда, когда на все входы поданы 1. Физически это можно реализовать последовательным соединением переключателей.
Условное обозначение логического элемента "И":
ЛОГИЧЕСКИЙ ЭЛЕМЕНТ "ИЛИ" (дизъюнктор)
Логическим элементом "ИЛИ" называется такой элемент, который на выходе выдает значение логической суммы входных сигналов.
На выходе дизъюнктор дает 1, если хотя бы на один из входов подана 1. Физически это можно реализовать параллельным соединением переключателей.
Условное обозначение:
Выход одного логического элемента можно соединить с входом другого логического элемента и таким образом получить цепочки из отдельных логических элементов. Каждую такую цепочку назовем логическим устройством. Соответствующую логическому устройству схему назовем функциональной схемой. Формой описания логических устройств является структурная формула.
ЗАДАЧА 1. Определить структурную формулу по функциональной схеме:
Ответ:
¬((АVB) V ¬B)
