Элементы математической логики
Начало исследований в области формальной логики было положено работами Аристотеля в IV в. до нашей эры. Однако математические подходы к этим вопросам впервые были указаны Дж. Булем. В честь него алгебру высказывания называют булевой (булевской) алгеброй, а логические значения − булевыми (булевскими). Основу математической логики составляет алгебра высказываний. Алгебра логики используется при построении основных узлов ЭВМ (дешифратор, сумматор, шифратор).
Алгебра логики оперирует с высказываниями. Под высказыванием понимают повествовательное предложение, относительно которого можно утверждать, истинно оно или ложно. Например, выражение «Расстояние от Москвы до Киева больше, чем от Москвы до Тулы» истинно, а выражение «5 < 3» - ложно, т. е. оба являются высказываниями. Отметим, что не любые предложения (выражения) являются высказываниями в логическом смысле, например: «Который час?».
Высказывания (логические переменные) принято обозначать буквами латинского алфавита (иногда − с индексами): 
( 
) и т. д. Если высказывание С истинно, это обозначается как С = 1 (С = t, true), а если оно ложно, то С = 0 (С = f, false).
Логические операции. В алгебре высказываний над высказываниями можно производить определенные логические операции, в результате которых получаются новые высказывания. Истинность результирующих высказываний зависит от истинности исходных и использованных для их преобразования логических операций.
|
|
|
Конъюнкция.Соединение двух (или нескольких) высказываний в одно с помощью союза И (AND) называется операцией логического умножения, или конъюнкцией. Эту операцию принято обозначать знаками «Ù, &» или знаком умножения «´». Сложное высказывание 
истинно только в том случае, когда истинны оба входящих в него высказывания. Истинность такого высказывания представлена в табл. 2.5.
Т а б л и ц а 2.5
Таблицы истинности конъюнкции и логической суммы высказываний
| Конъюнкция | Дизъюнкция | |||||
| А | В |
| А | В | 
| 
|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 |
Дизъюнкция. Объединение двух (или нескольких) высказываний с помощью союза ИЛИ (OR) называется операцией логического сложения, или дизъюнкцией. Эту операцию обозначают знаками «Ú» или знаком сложения «+». Сложное высказывание AÚB истинно, если истинно хотя бы одно из входящих в него высказываний (табл. 2.5).
В последнем столбце табл. 2.5 размещены результаты модифицированной операции ИЛИ − Исключающее ИЛИ (XOR). Отличается от обычного ИЛИ последней строкой.
Инверсия. Присоединение частицы НЕ (NOT) к некоторому высказыванию называется операцией отрицания (инверсии) и обозначается Ā (или 
А). Если высказывание А истинно, то Ā ложно, и наоборот (табл. 2.6).
|
|
|
Т а б л и ц а 2.6
Таблица истинности отрицания
| А | Ā |
| 0 | 1 |
| 1 | 0 |
Следует отметить, что помимо операций И, ИЛИ, НЕ в алгебре высказываний существует ряд других операций. Например, операция эквивалентности (эквиваленции) А~В (АºВ, A↔B, eqvB) (табл. 2.7).
Т а б л и ц а 2.7
Дата добавления: 2018-05-12; просмотров: 548; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!