 |
Основные логические операции и правила их выполнения.
|
|
|
|
Логические основы ЭВМ.
Среди задач, для решения которых привлекается ЭВМ, не мало таких, которые по традиции принято называть логическими. Кто не знает шуточной задачи о перевозке волка, козы и капусты с одного берега на другой. В логических задачах исходными данными являются не только числа, но и неожиданные, подчас весьма запутанные суждения.
Появлению и развитию математической логики способствовало стремление найти строгие правила обоснования и доказательства новых положений в науке. По мнению некоторых ее создателей, математическая логика должна была стать математическим аппаратом той части обычной логики, которую принято называть формальной.
Как и математика, формальная логика следует строгим правилам и не вникает в сущность анализируемых суждений. Одна из ее задач – установление формальных правил получения новых суждений из исходных, истинность которых не подвергается сомнению.
Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.
Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание "площадь поверхности Индийского океана равна 75 млн кв. км" в одной ситуации можно посчитать ложным, а в другой – истинным. Ложным – так как указанное значение неточное и вообще не является постоянным. Истинным – если рассматривать его как некоторое приближение, приемлемое на практике.
|
|
|
Употребляемые в обычной речи слова и словосочетания " не ", " и ", " или ", " если..., то ", " тогда и только тогда " и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими операциями (связками).
Высказывания, образованные из других высказываний с помощью логических связок, называются составными. Высказывания, не являющиеся составными, называются простыми (элементарными).
Так, например, из элементарных высказываний "Петров – врач", "Петров – шахматист" при помощи связки "и" можно получить составное высказывание "Петров – врач и шахматист", понимаемое как "Петров – врач, хорошо играющий в шахматы".
При помощи связки "или" из этих же высказываний можно получить составное высказывание "Петров – врач или шахматист", понимаемое в алгебре логики как "Петров или врач, или шахматист, или и врач и шахматист одновременно".
Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.
Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В – высказывание "Тимур летом отправится в горы". Тогда составное высказывание "Тимур летом побывает и на море, и в горах" можно кратко записать как А и В. Здесь "и" – логическая связка, А, В – логические переменные, которые могут принимать только одно из двух значений – "истина" или "ложь", обозначаемые, соответственно, "1" и "0".
Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:
В алгебре высказываний над простыми высказываниями определены следующие операции:
|
|
|
- " или " – логическое сложение (дизъюнкция);
- " и " – логическое умножение (конъюнкция);
- " не " – логическое отрицание.
- " если..., то " – логическое следование (импликация);
- " тогда и только тогда " – эквивалентность;
Рассмотрим эти логические операции.
Логическое сложение. Это сложное суждение, которое может быть составлено из нескольких простых высказываний. Своим названием обязано латинскому disjunctio – разоблачение, различие. Значение этого сложного высказывания будет истина тогда и только тогда, когда истинно хотя бы одно из входящих в него суждений. Пусть число входящих в него высказываний будет минимальным и равно двум. Обозначим эти высказывания А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.2, которая называется таблицей истинности.
Таблица 2.2
Таблица истинности
| А | В | Y | или | A | B | Y |
| истинно | истинно | истинно | ||||
| истинно | ложно | истинно | ||||
| ложно | истинно | истинно | ||||
| ложно | ложно | ложно |
Для обозначения дизъюнкции используется знак "+" и записывается
Y=А+В
Это логическое сложение, поэтому:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Логическое умножение. Это также сложное высказывание, которое может быть составлено из нескольких простых высказываний. Своим названием обязано латинскому conjunctio – соединяю. По определению конъюнктивным называется сложное высказывание, которое истинно тогда и только тогда, когда истинны все входящие в него высказывания. Как и в предыдущем случае рассмотрим пример с двумя высказываниями А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.3, которая называется таблицей истинности.
Таблица 2.3
Таблица истинности
| А | В | Y | или | A | B | Y |
| истинно | истинно | истинно | ||||
| истинно | ложно | ложно | ||||
| ложно | истинно | ложно | ||||
| ложно | ложно | ложно |
Для обозначения конъюнкции используется знак "*" и записывается
Y=А*В
и
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
|
|
|
1 * 1 = 1
Логическое отрицание. Присоединение частицы "НЕ" к сказуемому данного простого высказывания А называется операцией логического отрицания. Операция логическое отрицание над высказыванием А записывается А. Возможные наборы значений и итогового высказывания Y можно изобразить с помощью таблицы 2.4, которая называется таблицей истинности.
Таблица 2.4
Таблица истинности
| А | Y = А
| или | A | Y |
| истинно | ложно | |||
| ложно | истинно |
Логическое следование. Соединение двух высказываний в одно с использованием оборота речи "Если …, то…" называется операцией логического следования или импликацией. Операция импликации над высказываниями А и В записывается А → В (читается "А имплицирует В" или "В следует из А"). По определению импликацией называется сложное высказывание, которое ложно тогда и только тогда, когда А – истинно, а В – ложно. Рассмотрим пример с двумя высказываниями А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.5, которая называется таблицей истинности.
Таблица 2.5
Таблица истинности
| А | В | Y=А→В | или | A | B | Y=А→В |
| истинно | истинно | истинно | ||||
| истинно | ложно | ложно | ||||
| ложно | истинно | истинно | ||||
| ложно | ложно | истинно |
Эквивалентность. Соединение двух простых высказываний А и В в одно с использованием оборота речи, или, как принято говорить, связки "…тогда и только тогда…", называется операцией эквивалентности. Многоточием помечены высказывания, над которыми проводится операция эквивалентности. Операция эквивалентности над высказываниями А и В записывается А~B (читается "А эквивалентно В"). Эквивалентностью называется сложное высказывание, которое истинно тогда и только тогда, когда А и В – одновременно истинны или ложны. Рассмотрим пример с двумя высказываниями А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.6, которая называется таблицей истинности.
|
|
|
Таблица 2.6
Таблица истинности
| А | В | Y=А~В | или | A | B | Y=А~В |
| истинно | истинно | истинно | ||||
| истинно | ложно | ложно | ||||
| ложно | истинно | ложно | ||||
| ложно | ложно | истинно |
Три логические операции: дизъюнкция, конъюнкция и отрицание составляют "полную систему" – это значит, что любое логическое выражение можно составить с использованием только этих трех операций. Например, операцию импликации А→В можно заменить на 1-А+А*В, а операцию эквивалентность А~В заменить на 1-(А-В)2.
|
|
|
