Представление функций формулами. Равносильные формулы.

Факультет Кибернетики

Кафедра Автоматизированных систем

Носырева Л.Л.

Конспективный материал к лекциям

(рабочий вариант)

Для специальностей АСУ, МЭИ, ИП, АСОК

Часть 5

Иркутск 2006

БУЛЕВЫ ФУНКЦИИ

Основные понятия и определения.

    Определение булевой функции     таблицы истинности 2^ⁿ строк = Булевы функции от одной переменной Булевы функции от двух переменных

Определение1. Функциюf, принимающую одно из двух значений, 0 или 1, от n переменных, каждая из которых принимает одно из двух значений, 0 или 1, называется булевой функцией f(x₁,x₂,…, x_n) от n переменных. Иначе говоря, булевой называется функция вида: f: {0,1}^ⁿ→ {0,1}. Множество булевых функций от n переменных будем обозначать . Любая булева функция может быть задана в виде таблицы истинности. Если значение функции f зависит от n переменных то таблица истинности содержит 2^ⁿ строк, соответствующих всем различным комбинациям значений этих переменных. Пример 1.1. Рассмотрим, например, устройство, фиксирующее принятие некоторой резолюции комитетом «трех». Каждый член комитета при одобрении резолюции нажимает свою кнопку; если большинство членов согласны, то резолюция принимается, что фиксируется регистрирующим прибором. Устройство реализует функцию f(x₁, х₂, х₃), таблица истинности которой имеет вид таблицы1.   Таблица 1.

x1	х2	х3	f(x1, х2, х3)	x1	х2	х3	f(x1, х2, х3)

Число булевых функций от n переменных равно числу столбцов, которые можно сопоставить строкам таблиц истинности и равно , т.е. = .

Булевы функции от одной переменной приведены в таблицах 2,3от двух переменных в таблицах 4,5.

Таблица 2.

x	f0	f1	f 2	f 3

Таблица 3.

функция	обозначение	название
f0		Конст.0
f1	х	х
f2	х,	Отрицание х
f3		Конст.1

Таблица 4.

Переменные

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

x1

x2

f0

f1

f 2

f 3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

Таблица 5.

функция	обозначение	название
f0		константа нуль.
f1	x1 х2; x1 х2	конъюнкция
f2		левая коимпликация
f3
f4		правая коимпликация.
f5
f6		сложение по модулю два
f7		дизъюнкция
f8	;	функция Вебба, стрелка Пирса
f9		функция эквивалент­ности
f10	,	отрицание.
f11		правая импликация
f12	,	отрицание.
f13		левая импликация, импликация
f14		функция Шеффера.
f15		константа единица.

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

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

Представление функций формулами. Равносильные формулы.

Определение формулы Определение равносильности формул Основные эквивалентности между формулами:

Пусть F={f_1, f_2,…, f_m} -множество булевых функций. Формулой над F называется выражение вида f(t₁,t₂,…,t_n), где и t_i либо переменная, либо формула над F. Всякой формуле однозначно соответствует некоторая булева функция. Зная таблицы истинности для функций множества F можно вычислить таблицу истинности той функции, которую реализует данная формула.   Пример 2.1.     Пример 2.2.         Различные формулы могут иметь одинаковые таблицы истинности, т.е. одна и та же формула может иметь множество реализаций над одним и тем же базисом. Так возникает понятие эквивалентности (равносильности) формул. Формулы и называются равносильными , если совпадают их таблицы истинности, т. е. совпадают представляемые этими формулами функции и . Пример 2.3. Построив таблицы истинности формул , убеждаемся, что  

x	y

Легко видеть, что отношение ~ является отношением экви­валентности, т. е. оно рефлексивно , симметрично и транзитивно .

Основные эквивалентности между формулами:

1.	^,		(идемпотентность );
2.			(коммутативность );
3.	,		(ассоциативность )
4.	,		(дистрибутивность);
5.			(законы поглощения);
6.			(законы де Моргана);
7.		(закон двойного отрицания);
8.	;	;	законы, определяющие действия с константами 0 и 1
9.
10.
11.
12.
13.
14.
15.

Замечание. Знак в формулах обычно опускают, т.к. конъюнкцию называют еще логическим умножением.

Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значение 1 (соответственно 0).

Пример 2.3. Формула является одновременно выполнимой и опровержимой, поскольку .

Формула называется тождественно истинной, общезначимой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соот­ветственно 0) при всех наборах значений переменных, т. е. функ­ция f является константой 1 (константой 0).

Пример 2.4. Формула является тождественно истинной, а формула - тождественно ложной:

x

Если - тождественно истинная формула, то иногда пишут . В противном случае пишем .Таким образом, , и .

Очевидно, что:

1. формула тождественно ложна тогда и только тогда, когда тождественно истинна ();

2. формула опровержима тогда и только тогда, когда она
не является тождественна истинной ();

3. формула выполнима тогда и только тогда, когда она не является тождественно ложной.

Тождественно истинные (соответственно тожде­ственно ложные) формулы образуют класс эквивалентности по отношению ~.

Дата добавления: 2015-07-11