Логические основы ЭВМ, элементы и узлы 71

Высказывания, у которых таблицы истинности совпадают, на-

Зываются равносильными. Для обозначения равносильных высказы-

ваний используют jsHaK ≪=≫ (А = В). Рассмотрим сложное высказыва-

ние (А & В) \ (В & В) - табл. 1.23.

Таблица 1 23 Таблица истинности выражения (А & В) \ (В & В)

А

False

False

True

True

A

False

True

False

True

В

True

True

False

False

В

True

False

True

False

A&B

False

False

False

True

B&B

True

False

False

False

(B & B) | (A & B)

True

False

False

True

Если сравнить эту таблицу с таблицей истинности операции эк-

Вивалентности высказываний А и В, то можно увидеть, что выска-

зывания (А& В)\(В & В) и А~ В тождественны, т. е. А ~ В =

= (А & В) (В& В).

В алгебре высказываний можно проводить тождественные пре-

Образования, заменяя одни высказывания равносильными им дру-

Гими высказываниями.

Свойства операций. Исходя из определений дизъюнкции, конъ-

Юнкции и отрицания, устанавливаются свойства этих операций и

Взаимные распределительные свойства. Приведем примеры некото-

Рых из этих свойств.

Коммутативность (перестановочность)

А л В = В л А

Av B=£v A

Закон идемпотентности

А&А = А, AvA = A.

Двойное отрицание

А=А

Сочетательные (ассоциативные) законы

Av (Bv C) = (Av B)v С = Av Bv С

Л л (Д л С) = (Л л, б) л С = Л л 5 л С

Распределительные (дистрибутивные) законы

A^(Bv С)=(Лл B)v (А А С)

A v (В л С) = (A v В) л (A v С)

Поглощение

х v (х л у) = х

х л (х v у) = х

Глава 1. Вычислительные приборы и устройства..

Склеивание

(х л у) v (Зс л у) = у

(xv.у) л (xv У)=У

Операция переменной с ее инверсией

х v х = 1

х л х = О

Операция с константами

х v 0 = х, xv 1 = 1

х л\ = х, л: л 0 =0

Законы Де Моргана

1. Л& 5 = A v В (условно его можно назвать 1-й);

2. Av В = А&В (2-й) —описывает результаты отрицания пере-

Менных, связанных операциями И, ИЛИ.

Высказывания, образованные с помощью нескольких операций

Логического сложения, умножения и отрицания, называются слож-

Ными. Истинность всякого сложного высказывания устанавливается