Логические операции
Компьютер выполняет не только арифметические, но и логические операции, используя понятие истины (1, True, T) или ложь (0, False, F). Большое количество технических устройств компьютера, а также программных систем (экспертных, поддержки управленческих решений, интеллектуальных и т.д.) работают на основании математической логики, из всех разделов которой наибольшую популярность приобрели исчисление высказываний и исчисление предикатов.
Исчисление высказываний.
Цель исчисления высказываний состоит в определении их истинности или ложности на основании исходных посылок. В основе такого рода исчислений находится понятие «высказывание», связном повествовательном предложении, о котором можно сказать, истинно оно или ложно. Например, среди следующих предложений:
- Два умножить на три равно шесть.
- 5 > 7.
- Река Волга впадает в Балтийское море.
- Какая завтра будет погода?
высказываниями являются 1, 2 и 3 предложения и среди них лишь 1 будет истинным. Пример 4 не является высказыванием, так как нельзя сказать истинно оно или ложно.
Логику высказываний не интересует то, о чем идет речь в высказывании. Ее интересует лишь его истинность или ложность, так как она необходима для рассмотрения суждений без учета их внутренней структуры. Логика высказываний использует содержательные символы – выражения языка, имеющие смысл даже в том случае, если они взяты сами по себе. Высказывания обозначаются большими буквами латинского алфавита. Если высказывание A истинно, то пишут A = 1, если ложно, то используют запись A = 0.
На естественном языке из простых связных повествовательных предложений с помощью некоторых стандартных связок можно образовывать составные предложения. В логике высказываний таким связкам соответствуют логические операции.
Операция отрицания
Операция логического отрицания осуществляется над одним высказыванием. Выполнить операцию логического отрицания (обозначается ) – значит получить из данного высказывания новое, присоединяя слова «неверно, что …» ко всему высказыванию. Например, если А = «Луна спутник Земли», то = «неверно, что Луна спутник Земли», что ложно. Истинность высказывания определяется таблицей:
|
Отрицание |
|
|
А |
|
|
1 |
0 |
|
0 |
1 |
Отсюда следует, что отрицание высказывания истинно тогда и только тогда, когда высказывание А ложно.
Операция конъюнкции
Конъюнкция (логическое умножение) соответствует союзу 'и' в русском языке. Конъюнкция двух высказываний истинна тогда и только тогда, когда оба составляющих высказывания истинны. Например, пусть у нас есть два истинных высказывания А= «Земля круглая» и В= «Луна –спутник Земли», тогда их конъюнкцией будет так же истинное высказывание «Земля круглая и Луна – спутник Земли» (А=1, В=1; 1·1=1). В случае, если хотя бы одно из высказываний ложно, например В = «Марс - спутник Земли», их конъюнкция «Земля круглая и Марс – спутник Земли» так же будет ложным высказыванием (А=1, В=0; 1·0)=0. Истинность конъюнкции определяется таблицей:
|
Конъюнкция |
||
|
А |
В |
А×В |
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Операция дизъюнкции
Дизъюнкция (логическое сложение) соответствует союзу 'или' в русском языке.
Например, высказывание A – «Декабрь – зимний месяц», В – «В январе сильный мороз», определим высказывание A+B как «Декабрь – зимний месяц или в январе сильный мороз» (А=1; В=1 или В=0; 1+1=1 или 1+0=1). Дизъюнкция истинна, если хотя бы одно из высказываний истинно. Установить истинность логической суммы можно с помощью следующей таблицы:
|
Дизъюнкция |
||
|
А |
В |
А+В |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
То есть дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны.
Эквиваленция высказываний А, В - это высказывание, обозначаемое и определяемое следующей таблицей:
Эквиваленция истинна тогда и только тогда, когда образующие её высказывания А, В имеют одинаковые значения.
Импликация
Импликации соответствуют конструкции 'Если ..., то ... ' (' Из ... следует ...').
Импликация высказываний А и В обозначается как . Ее истинность определяется следующей таблицей:
|
Импликация |
||
|
А |
В |
|
|
0 |
0 |
1 |
|
1 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
1 |
1 |
Импликация ложна тогда и только тогда, когда А - истина, В - ложь.
Допустим А = «Цены высоки» и В = «Товаров продано мало». Тогда импликация является истинным. Элементы высказывания, образующего импликацию, имеют специальные названия: А - посылка (гипотеза, антецедент), В - заключение (вывод, консеквент ).
Формулы исчисления высказываний. Таблицы истинности
Формулы исчисления высказываний – это высказывания, которые могут быть получены из элементарных высказываний (например A, B, 1, 0) посредством применения логических операций отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции. Формулы необходимы для исчисления истинности или ложности составных высказываний, то есть решения логических задач.
Особое значение в логике исчисления высказываний имеют тождественные высказывания и эквивалентные высказывания (формулы де Моргана). Если высказывания в таблице истинности характеризуются либо одними единицами, либо только нулями, то это означает, что они, либо всегда истинны, либо ложны, независимо от истинности входящих в них высказываний. Например, высказывание всегда истинно, а высказывание всегда ложно. Сложные высказывания, истинные при любых значениях входящих в них других высказываний, называются тождественно истинными, а высказывания, ложные при любых значениях входящих в них других высказываний, называются тождественно ложными.
