Логика и её машинная реализация

Логика по существу является наукой о методах распознавания истинности или ложности отдельных высказываний. Символическая логика занимается изучением функций от переменных, принимающих одно из двух значений: «истина» или «ложь». Возможные значения функций принадлежат тому же множеству. Утверждения и доказательства символической логики обычно базируются на так называемой булевой алгебре, представляющей собой множество правил, отношений и операций, использующихся для определения истинности высказываний. В этом разделе мы познакомимся с операциями булевой алгебры, а также с некоторыми другими, имеющими большое применение в приложениях. Затем мы рассмотрим вопросы, связанные с конкретной реализацией логики в ЭВМ.

ОПЕРАЦИИ СИМВОЛИЧЕСКОЙ ЛОГИКИ

Нам будет достаточно рассмотреть четыре логические операции. К числу таких операций принадлежат И (AND), СЛОЖЕНИЕ ПО МОДУЛЮ 2 (exclusive OR — XOR), ИЛИ (OR) и НЕ (NOT). Первые три операции являются бинарными, т. е. имеют по два аргумента и одно значение. Операция НЕ является унарной операцией, она напоминает унарную арифметическую функцию sign.

Операция И (AND). В английском языке слово И (AND) используется для связки двух простых предложений в сложное. В логике И имеет приблизительно тот же смысл, однако здесь существуют точные правила установления истинности результирующего предложения. Предположим, что предложение имеет вид

[предложение 1] и [предложение 2]

и что предложения 1 и 2 могут независимо друг от друга принимать по одному из значений «истина» или «ложь». Пусть А является значением предложения 1, а В — значением предложения 2. В этом случае результирующее предложение можно записать так:

A AND В

Нас интересует, в случае каких А и В результирующее предложение окажется истинным. Здесь можно воспользоваться аналогией с применением И (AND) в обычном английском языке. Результирующее предложение

[предложение 1] и [предложение 2]

истинно, когда оба предложения 1 и 2 истинны. Во всех остальных случаях значением сложного предложения является «ложь».

Пусть в качестве предложения 1 выступает предложение

«бит есть двоичная цифра»

а в качестве второго предложения — предложение

«капуста есть овощ»

Сложное предложение

[предложение 1] и [предложение 2]

очевидно, истинно. С другой стороны, если бы в качестве предложения 2 выступало предложение

«капуста есть булыжник»

то результирующее предложение

[бит есть двоичная цифра] и [капуста есть булыжник]

имело бы ложное значение.

Рис. 14.1. Матрицы истинности для логических операций AND, OR, XOR и NOT. (Здесь Т (True) означает «истина», F (False) — «ложь».)

Аналогично, если А и В — логические переменные, то выражение

A AND В

истинно лишь в случае истинности обоих переменных. Более наглядно это можно записать так:

Более компактный способ представления логических операций состоит в использовании матрицы истинности. На рис. 14.1, а приведена матрица истинности операции И. В верхней строке указываются всевозможные значения переменной А, в крайнем левом столбце — значения переменной В. Значение A AND В отыскивается на пересечении строки и столбца, помеченных значениями соответственно В и А.

Операция ИЛИ (OR). Операции типа ИЛИ не имеют в английском языке двух разных слов для своего обозначения. В английском языке обе они имеют эквивалент OR. Что именно имеется в виду, зависит от контекста. Например,

(предложение 1) или (предложение 2) или и то и другое

соответствует операции OR. Случай истинности обоих предложений здесь учитывается. Результатом выполнения операции ИЛИ является «истина», если значение, по крайней мере, одного аргумента есть «истина».

Лишь тогда, когда А и В одновременно ложны, результатом операции является «ложь».

Операция СЛОЖЕНИЕ ПО МОДУЛЮ 2(XOR).XOR (ИСКЛЮЧАЮЩЕЕ ИЛИ) исключает возможность одновременной истинности обоих аргументов. Аналогом XOR может служить такая конструкция обычного языка:

одно из двух: (предложение 1) или (предложение 2) но не оба

Другими словами, A XOR В принимает значение «истина» только в том случае, когда один из аргументов, А или В, есть «истина». В случае истинности обоих значение A XOR В есть «ложь».

Операция НЕ (NOT). Применение НЕ к некоторой переменной дает просто ее логическое дополнение. Если А есть «истина», то NOT А — «ложь», и наоборот, если А — «ложь», то NOT А — «истина».

 



 
Оглавление
Логика и её машинная реализация
Реализация логики
Статьи раздела