WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«42. Булева алгебра. Функции алгебры логики 1 Булевы функции Будем рассматривать булевы функции функции, аргументы и значения которых ...»

Е.В.Просолупов

42. Булева алгебра. Функции алгебры

логики

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

Будем рассматривать булевы функции функции, аргументы и значения

которых принимают значения истина и ложь. Истину и ложь будем

обозначать соответственно 1 и 0. Таким образом функция n аргументов

f есть

f : {0, 1} {0, 1}... {0, 1} {0, 1}.

n

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

обозначать буквами x, y и z, возможно с индексами. Множество всех

булевых функций (функций алгебры логики) будем обозначать P2.

Пример 1.1. Табличное задание функции f :

x y z f (x, y, z) Всего существует 23 различных наборов значений трех переменных.

Если их нумеровать от 0 до 23 1, то набор с номером i оказывается представлением числа i в двоичной системе счисления. Всего различных функций от 3-х аргументов 22 В общем случае число строк в таблице для функции от n аргументов n равно 2n. Число различных булевых функций от n аргуменов 22.

Определение 1.1. Будем говорить, что функция f (x1, x2,..., xn ) не зависит существенно от xn (xn несущественная переменная функции f (x1, x2,..., xn )), если на любых значений 1, 2,..., n1 {0, 1} выполняется равенство f (1, 2,..., n1, 0) = f (1, 2,..., n1, 1).

Переменные функции f, которые не являются несущественными, называют существенными переменными и говорят, что функция f существенно от них зависит.



Пример 1.2.

Функция f из примера 1.1 не зависит существенно от переменной y.

Определение 1.2. Будем говорить, что две функции f (x1, x2,..., xk ) и g(x1, x2,..., xl ) равны, если после удаления всех несущественных переменных получаются функции с одинаковыми таблицами. В таком случае будем писать f = g.

2 Формулы Выберем некоторую сисстему функций из P2 : P = {f1, f2,..., fk } P2, k 1. Назавем функции из системы P элементарными функциями.

Тогда формула над {f1, f2,..., fk } определяется рекурсивно:

Определение 2.1. 1. Если f (x1,..., xn ) P, то f (x1,..., xn ) формула.

2. Если f (x1,..., xn ) P и U1, U2,..., Un формулы или логические пременные, то f (U1,..., Un ) формула.

Замечание 2.1. Мы определили формулу над P. Формула всегда мыслится в связи с каким-то указанным множеством элементарных функций.

Каждой функции можно однозначно сопоставить функцию:

1. Если U = f (x1,..., xn ) P, то формуле U сопоставляется функция fU = f (x1,..., xn ).

2. Пусть U = f (U1,..., Un ), где f (x1,..., xn ) P и U1, U2,..., Un формулы или логические пременные. Тогда fU = f (fU1,..., fUn ), где fUi функция, сопоставленная формуле Ui, если Ui формула, и fUi = xi, если Ui = xi логическая переменная.

Будем говорить, что формулы U и B Определение 2.2.

эквивалентны и писать U = B, если fU = fB с точностью до несущественных переменных.

Рассмотрим основные функции, используемые в качестве элементарных функций в алгебре логики.

Всего существует четыре различные функции от одной переменной:

тождественный ноль f (x) = 0; тождественная единица f (x) = 1;

тождественная функция или тождественный x f (x) = x; отрицание x или "не x" f (x) = ¬x, так же обозначается x.

x 0 1 x ¬x Из них тождественный ноль и тождественная единица не зависят существенно от x. То есть фактически это две функции без аргументов константы: f = 0 и f = 1.





Рассмотрим основные булевы функции от двух переменных.

x y x y x y x y x y x y x|y x y f (x, y) = x y дизъюнкция, логическое "или".

f (x, y) = x y конъюнкция, логическое "и", логическое умножение.

Также можно использовать обозначения x&y или xy.

f (x, y) = x y сложение по модулю два, логическое исключающее "или". Также можно использовать обозначение x + y.

f (x, y) = x y импликация, "если, то". Также можно использовать обозначение x y.

f (x, y) = x y эквивалентность. Также можно использовать обозначение x y.

f (x, y) = x | y штрих Шеффера.

f (x, y) = x y стрелка Пирса.

Всего, как мы помним, существует 16 различных функций от двух переменных. Мы выбрали 7, существенно зависящих от обоих переменных и имеющих наибольшее значение. Добавив к ним функции от одной переменной и константы (функции от 0 переменных) получим систему элементарных функций P = {0, 1, x, x, x y, xy, x y, x y, x y, x|y, x y}.

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

Пример 2.1. Рассмотрим пример формулы над P :

U = (((xy) (xz)) (xz)).

В этой записи слишком много скобок.

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

Кроме того можно убедиться, что операции,,, являются ассоциативными. Таким образом, вместо x (y z) или (x y) z можно писать x y z, если {,,, }. Операции, |, не являются ассоциативными.

–  –  –

Таким образом, формула U задает тождественно истинную функцию.

Очевидно, что формула B = U = (y x) (x 1) y = 1 = 0, то есть B задает тождественно ложную функцию.

Определение 3.1. Формула, задающая тождественно истинную функцию, называется тавталогией.

Определение 3.2. Формула, задающая тождественно ложную функцию, называется противоречием.

Определение 3.3. Формула называется выполнимой, если для нее существует набор аргументов, на котором она принимает значение 1.

–  –  –

где K1, K2,..., Ks различные конъюнкты, то говорят, что f представлена в дизъюнктивной нормальной форме (ДНФ).

Если в каждый Ki входят все переменные x1,..., xn, то говорят, что f представлена в совершенной дизъюнктивной нормальной форме (СДНФ).

Утверждение 4.2. Пусть f (x1,..., xn ) P2. Если f = 0, то она представима в виде СДНФ, причем единственным образом (с точностью до перестановки конъюнктов).

Замечание 4.2. Из утверждения 4.1 мы получили формулу (1), которую удобно использовать для построения СДНФ для функции f = 0.

Теперь для построения СДНФ согласно формуле (1) необходимо выбрать каждый набор (1,..., n ), для которого f (1,..., n ) = 1, и сопоставить ему коньюнкт x1 · · · xn совершенной дизъюнктивной n нормальной формы.

Пример 4.1. Рассмотрим функцию f (x, y, z), заданную таблицей:

–  –  –

6 Полнота системы функций Определение 6.1. Система функций P P2 называется полной, если любую функцию из P2 можно представить в виде формулы над P.

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

–  –  –

Утверждение 7.1. Класс функций T0 замкнут.

Определение 7.2. Пусть f (x1,..., xn ) P2. f называют функцией, сохраняющей единицу, если f (1,..., 1) = 1.

Множество всех функций сохраняющих 1 назовем T1 :

–  –  –

Утверждение 7.2. Класс функций T1 замкнут.

8 Двойственность Определение 8.1. Пусть f (x1,..., xn ) P2. Двойственной функцией к функции f называется f (x1,..., xn ) = f (x1,..., xn ).

–  –  –

Определение 8.2. Функция f (x1,..., xn ) P2 самодвойственная, если f (x1,..., xn ) = f (x1,..., xn ).

Обозначим за S множество всех самодвойственных функций:

–  –  –

Будем говорить, что n строго предшествует n и обозначать n n, если n n и n = n.

Будем говорить, что n непосредственно предшествует n и обозначать n n, если если n n и не существует набора n такого, что n n n.

–  –  –

где каждая пара наборов n (i 1) и n (i) отличаются только в одной позиции, i = 1, t. Это не трудно сделать, последовательно заменяя каждую позицию, в которой наборы n и n разтличаются с нуля на единицу. Поскольку f (n ) = 1 и f ( n ) = 0, найдется такое k, что n (k 1) = 1 и n (i) = 0. Такая ситуация возвращает нас к пункту

a) доказательства.

–  –  –

f (x1,..., xn ) = = x1 x2 f1,2 (x3,..., xn ) x1 f1 (x3,..., xn ) x2 f2 (x3,..., xn ) f0 (x3,..., xn ), причем 3,..., n : f1,2 (3,..., n ) = 1. Действительно, такие 3,..., n существуют, поскольку, если бы f1,2 (3,..., n ) = 0, 3,..., n {0, 1}, то функция f приняла бы вид f (x1,..., xn ) = x1 f1 (x3,..., xn ) x2 f2 (x3,..., xn ) f0 (x3,..., xn ), что противоречит нашему предположению, что {1, 2} I и (I ) = 1.

Рассмотрим

–  –  –

Доказательство. Пусть f0, f1, fS, fM, fL P такие функции, что f0 T0, f1 T1, fS S, fM M, fL L (некоторые из / / / / / функций могут совпадать). Проведем доказательство в несколько этапов, последовательно доказав, что с помощью суперпозиций функций из P можно выразить систему {¬, }, чем и докажем полноту P.

1) Покажем, что с помощью f0, f1, fS можно получить 0 и 1.

a) Пусть f0 (1,..., 1) = 1. Пусть (x) = f0 (x,..., x). Тогда (0) = (1) = 1. Значит (x) = 1 и, имея единицу, можно получить вторую константу 0 = f1 (1,..., 1).

b) Пусть теперь f0 (1,..., 1) = 0. Тогда (x) = f0 (x,..., x) = x.

Подставляя в fS x и x по лемме о несамодвойственной функции получаем константу 0 или 1 и с помощью x получаем вторую константу.

2) По лемме о немонотонной функции, подставляя константы в fM можно получить ¬x.

3) Используя fL, константы и ¬x, по лемме о нелинейной функции можно получить x y.

Так как {¬, } полная системя функций, то и система P полная.

Похожие работы:

«Сервис «Корпоративное бюджетирование» Руководство сотрудника управляющей компании WEB-интерфейс 2.0.23 Сервис «Корпоративное бюджетирование» Содержание Назначение сервиса «Корпоративное бюджетирова...»

«Портрет святителя Димитрия Ростовского из собрания Сергиево-Посадского музея-заповедника О.И. Зарицкая Среди портретов иерархов, хранящихся в Сергиево-Посадском музеезаповеднике, выделяется полотно с изображением ростовского Святителя Димитрия Тупта...»

«ХОРОШО ОБРАЗОВАННЫЕ, НРАВСТВЕННЫЕ ЛЮДИ – СИЛА РОССИИ Мухсинова Л.Х. Оренбургский государственный университет, г. Оренбург XXI век открыл новую эру в образовании оно становится непрерывным процессом, который бу...»

«ЗАДАНИЯ к практическим занятиям по дисциплине «Функциональное и логическое программирование» Практическое занятие №1. Рекурсивные структуры данных (списки) (Prolog) Практическое занятие №2. Рекурсивные структуры данных (деревья) (Prolog) Пр...»

«К 125-летию со дня рождения и 70-летию со дня кончины священника Павла Флоренского ФИЛАРЕТ, митрополит Минский и Слуцкий, Патриарший Экзарх всея Беларуси, Председатель редколлегии «Богословских трудов» Священник Павел Флоренский Вспоминаю, как в 2006 году ко мне, председателю Богословской Синодальной комиссии, впервые обратил...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Санкт – Петербургский государственный универс...»

«УЧЕНЫЕ ЗАПИСКИ КАЗАНСКОГО УНИВЕРСИТЕТА Том 156, кн. 1 Гуманитарные науки 2014 УДК 111 НЕБЕССМЫСЛЕННОСТЬ АБСУРДА И ОГРАНИЧЕННОСТЬ СТРОГОЙ МЫСЛИ А.Н. Фатенков Аннотация В статье эскизно представлена онтогносеологическая концепция, основу которой составляют тезисы о том, что мир изнача...»








 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.