Булевы функции

Функция , у которой аргументы пробегают множество {0,1} и которая принимает значение из того же множества {0,1}, называется функцией алгебры логики или булевой функцией.

Особое значение имеют так называемые элементарные булевы функции. Двухместными элементарными булевыми функциями являются конъюнкция, дизъюнкция, импликация, сумма по модулю 2, эквиваленция, штрих Шеффера и стрелка Пирса. Символы А и B из табл. 4.2 следует в этом случае толковать как булевы переменные {0,1}.

Имеются две одноместные булевы функции, зависящие от x: тождественная функция и отрицание . Это элементарные функции (табл. 4.3).

 

 

Таблица 4.3

x

 

Имеются две нуль-местные элементарные булевы функции: это константы 0 и 1. Каждой пропозициональной формуле можно сопоставить булеву функцию. Булева функция , сопоставленная пропозициональной формуле A, называется функцией истинности формулы A. Любую такую функцию можно описать с помощью соответствующей таблицы истинности (примеры – табл. 4.3, табл. 4.4, табл. 4.5).

Пусть и – функции истинности формул P и Q; пусть {} – множество тех переменных, которые встречаются хотя бы в одной из функций и . Пропозициональные формулы P и Q называются эквивалентными, если на всяком наборе () значений переменных значения функций и совпадают (эквивалентность обозначают как: PQ).

Пример 4.3.Покажем эквивалентность выражений

PAB и QAB.

Для этого построим таблицу истинности (табл. 4.4).

Таблица 4.4

A	B	(A, B) PAB	(A, B) QAB

 

Поскольку (A, B) = (A, B), то P Q.

Пример 4.4.Покажем эквивалентность выражений

PA(BC) и Q(AB)(AC).

Для этого снова построим таблицу истинности (табл. 4.5).

Таблица 4.5

A	B	C	(A, B, C) PA(BC)	(A, B, C) Q(AB)(AC)

 

Поскольку (A, B, C) =(A, B, C), то P Q. Как можно видеть, в примере 4.3 используются двухместные функции истинности, а в примере 4.4 – трехместные.

 

Основные эквивалентности:

AA – правило снятия двойного отрицания;

AAA – идемпотентность конъюнкции;

AAA – идемпотентность дизъюнкции;

A*B B*A – коммутативность связки * (символ * является общим

обозначением для связок: ,, );

(A*B)*C A*(B*C) – ассоциативность связки *;

A(BC )(AB)(AC) – дистрибутивность («distributivus» – распределительный) конъюнкции относительно дизъюнкции;

A( BC)(AB)(AC) – дистрибутивность дизъюнкции относительно конъюнкции;

(AB)AB и (AB)AB – законы де Моргана;

A(AB)A и A(AB)A – законы поглощения;

A(AB)AB и A(AB)AB;

ABAB;

(AB)(AB)(AB);

AAFalse – закон противоречия;

AATrue – закон исключенного третьего;

ATrueA;

ATrueTrue;

AFalseFalse;

AFalseA;