48. Булева алгебра и основные логические тождества.

Булевой алгеброй называется непустое множество A с двумя бинарными

операциями (аналог конъюнкции), (аналог дизъюнкции), унарной

операцией (аналог отрицания) и двумя выделенными элементами: 0 (или

Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны

следующие аксиомы:

ассоциативность

коммутативность

законы

поглощения

дистрибутивность

дополнительность

Первые три аксиомы означают, что (A, , ) является решёткой. Таким

образом, булева алгебра может быть определена как дистрибутивная

решётка, в которой выполнены две последние аксиомы. Структура, в которой

выполняются все аксиомы, кроме предпоследней, называется псевдобулевой

алгеброй.

Булева алгебра имеет практическое приложение в цифровой технике,

основанной на двоичной логике. Как существуют булевы функции, так

существуют и булевы производные. Булевы производные - единственный

математический аппарат для разработки тестов цифровой техники.

Основные тождества

В данном разделе повторяются свойства и аксиомы, описанные выше с

добавлением ещё нескольких.

Сводная таблица свойств и аксиом, описанных выше:

; . 1 коммутативность

; . 2 ассоциативность

3.1 конъюнкция

относительно дизъюнкции

3.2 дизъюнкция

относительно конъюнкции 3

дистрибутивность

; . 4

дополнительность

57

(свойства

отрицаний)

; .

5 законы де

Моргана

; .

6 законы

поглощения

; .

7 Блейка-

Порецкого

; .

8

Идемпотентность

.

9 инволютивность

отрицания

; .

10 свойства

; . констант

дополнение 0 есть 1 ; дополнение 1 есть 0 .

; . 11 Склеивание

58

49. Пропозициональные буквы, связки и формы (формулы логики

высказываний). Построение таблиц истинности

Символы , &, ∨, ⇒, ≡ называются пропозициональными связками.

Заглавные буквы алфавита (А,В,С,...) и те же буквы с числовыми индексами

(А1,А2,...,В1,В2,...,С1,С2,...) называются пропозициональными буквами.

Считается, что каждая пропозициональная буква может принимать значение

И либо Л.

Выражением называется конечная последовательность определенных

символов. Например, ∨А&∨В - выражение, построенное из символов ∨, &, А и

В, а ?§!! - выражение, построенное из символов ?, § и !.

Пропозициональная форма представляет собой выражение, полученное

по некоторым правилам из пропозициональных букв с помощью

пропозициональных связок.

Индуктивное определение пропозициональной формы:

1) все пропозициональные буквы суть пропозициональные формы,

2) если А и В пропозициональные формы, то ( А), (А&В), (А∨В), (А⇒B), (А≡B)

тоже пропозициональные формы,

3) только те выражения являются пропозициональными формами, для

которых это следует из пп.1,2.

Примеры пропозициональных форм: A, ( В), ((А&В)⇒(C)), ((( А)∨В)≡С).

Пропозициональные формы часто называют формулами логики

высказываний.

Жирные заглавные буквы латинского алфавита (А,В,C ,...) или те же буквы с

числовыми индексами (А1,А2,...,В1,В2,...,С1,С2,...) употребляются для

обозначения произвольных пропозициональных форм, тогда как обычное

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

Истинностной функцией от n аргументов называется n-аргументная функция,

принимающая одно из двух значений: И либо Л, когда ее аргументы

пробегают те же значения.

Составное (сложное) высказывание, образованное с помощью введенных

операций , &, ∨, ⇒, ≡ будет истинным либо ложным в зависимости от

значений исходных высказываний. Следовательно, полученное составное

высказывание порождает некоторую истинностную функцию.

Как определено выше, каждая пропозициональная буква может принимать

значения И либо Л. Будем считать, что пропозициональные формы (А),

(А&В), (А∨В), (А⇒В) и (А ≡Β) имеют те же таблицы истинности, что и

обозначаемые таким образом высказывания (см.§1). Тогда каждому

распределению (истинностных) значений И и Л пропозициональных букв,

входящих в пропозициональную форму, соответствуют согласно таблицам

истинности для пропозициональных связок некоторые истинностные значения

этой пропозициональной формы.

Таким образом, каждая пропозициональная форма порождает некоторую

функцию, принимающую значение Л или И в зависимости от истинностных

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

пропозициональная форма порождает некоторую истинностную функцию.

Заметим, что пропозициональная форма не является высказыванием. По

определению пропозициональная форма - это выражение, построенное из

59

пропозициональных букв, т.е. букв А, В, С,..., А1 ,А2 ,..., В1 ,В2 ,..., С1,С2,... с

помощью пропозициональных связок согласно правилам 1), 2), 3) и ничего

более. В частном случае пропозициональные буквы могут обозначать

высказывания, пропозициональные связки - логические операции, тогда

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

Истинностное значение полученного высказывания можно определить с

помощью таблиц истинности.

Так как добавление каждой новой пропозициональной буквы увеличивает

количество строк в таблице истинности вдвое, то пропозициональная форма,

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

истинности с 2n строками. Например, для формы (((А&В)∨С)⇒А) имеем

следующую таблицу истинности.

А B C (A&B) ((А&В)∨

С)

(((А&В)∨

С)⇒А)

Л Л Л Л Л И

Л Л И Л И Л

Л И Л Л Л И

Л И И Л И Л

И Л Л Л Л И

И Л И Л И И

И И Л И И И

И И И И И И

60