Логические операции

Алгебра высказываний

Действия и преобразования, применяемые в обычной алгеб­ре, в которой буквами обозначаются числа, основываются на не­большом числе определений и формул.

• Существует арифметическое действие, называемое сложе­нием и обозначаемое знаком +. Устанавливается, что для каждой пары данных двух чисел а и b существует единственное опреде­ленное число с, называемое суммой чисел а и Ь. Действие сло­жения обладает переместительным и сочетательным свойствами. Отсюда формулы:

1) a + b = с (существование единственной суммы чисел а и b)

2) a + b = b + а (переместительное свойство);

3) a + (b + с) = (a + b ) + с (сочетательное свойство).

• Существует второе арифметическое действие, называемое умножением и обозначаемое знаком х или * (последний знак при употреблении буквенных обозначений обычно не ставится). Действие умножения обладает теми же свойствами, что и сложе­ние: для каждых двух чисел а и b существует определенное един­ственное произведение ab, и действие умножения обладает пере­местительным и сочетательным свойствами, которые дают фор­мулы:

4) ab = d (существование произведения);

5) ab = ba (переместительное свойство);

6) a(bc) = (ab)c (сочетательное свойство).

Сложение и умножение обладают распределительным свой­ством: чтобы умножить сумму двух слагаемых на третье число, можно умножить каждое слагаемое отдельно на это число, и по­лученные произведения сложить;

7) (a + b)c = ac + bс (распределительное свойство).

• Существует такое число, обозначаемое знаком 0 (нуль), при сложении которого с любым числом а получается в сумме то же число а, а при перемножении его (т. е. нуля) с любым числом а получается в произведении 0. Отсюда формулы:

8) a + 0 = 0 + a = a;

9) a – 0 = 0 – a = 0.

• Существует еще число, обозначаемое знаком 1 и называе­мое единицей, при перемножении с которым любого числа а по­лучается в произведении то же число а:

10) а х 1 = 1 х а = а.

Отмеченные десять формул являются основными законами обычной арифметики и алгебры.

Джордж Буль, давший в 1847 г. первое изложение алгебры логики, сделал предположение, что буквы в записанных десяти формулах обозначают не числа, а высказывания, и показал, что можно выбрать такие определения действий сложения и умно­жения, при которых все десять формул остаются в силе.

Приоритет логических операций:

1) инверсия 2) конъюнкция 3) дизъюнкция 4) импликация 5) эквивалентность

1. Конъюнкция: А ^ В или А ∙ В (логическое умножение, чита­ется как союз «и»)

А	В	А ^ В

2. Дизъюнкция: A v В или А + В (логическое сложение, чита­ется как союз «или»)

А	В	A v В

3. Отрицание: . Иногда отрицание называют функцией Вебба или функцией Даггера.

4. Импликация или логическое следование (читается: если А, то В). Обозначается А → В

А	В	А-> В

5. Эквиваленция, или тождественность: А↔В (А ~ В) (чита­ется: А тогда и только тогда, когда В)

A	B	А↔В

При решении логических задач используют приемы:

1. построение таблиц истинности;

2. решение логических уравнений.

Построение таблиц истинности

Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре:

(0, 0), (0, 1), (1, 0), (1, 1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

То есть, количество наборов = 2ⁿ, где n – количество высказываний (переменных).

Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.

Дата добавления: 2014-10-17