АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Опр. 1. (первая теорема о представлении булевых функций)

(первая теорема о представлении булевых функций). Пусть f (X1 ,…, Xk) – k-местная булева функция (k 1). Если f не равна тождественно 0, то такая формула F, зависящая от списка переменных <X1, , Xk> и находящаяся в СДНФ относительного этого списка, что F выражает собой функцию f. формула F определена однозначно с точностью до перестановки дизъюнктивных членов.

Докажем сначала вспомогательное утверждение. При s = 1под Аs будем подразумевать формулу А, а при s = 0 –формулу А. с каждой оценкой списка переменных <s1, , sk>, будем ассоциировать элементарную конъюнкцию Х1s1 Хksk.

Лемма.

Конъюнкция Х1s1 Хksk ассоциированная с оценкой <s1, , sk>, обращается в 1 на одной и только на одной оценке списка переменных <X1, , Xk>, а именно на оценке <s1, , sk>.

И в самом деле, на оценке <s1, , sk> формула Х1s1 Хksk принимает значение 1, так как каждый ее конъюнктивный член Хlsl принимает значение 1. Действительно, возможны два случая: либо sl(1 l k) есть 1, и тогда Хlsl есть Хl, либо sl есть 0, и тогда Хlsl есть Хl. в каждом из этих случаев Хlsl на оценке <s1, , sk> принимает значение 1.

С другой стороны, пусть оценка <t1, , tk> не совпадает с оценкой <s1, , sk>. Тогда при некотором l (1 l k) sl tl.

Возможны два случая:

1) sl = 1, tl = 0

2) sl = 0, tl = 1

В первом случае Хlsl есть Хl, а во втором Хlsl­ Хl. В любом случае Хlsi на оценке <t1, , tk> принимает значение 0, а значит, и вся элементарная конъюнкция Х1s1 Хksk принимает значение 0. Лемма доказана.

 

Пусть теперь функция f (X1 ,…, Xk) задана таблицей. Выберем из таблицы все строки, соответствующие оценкам, на которых f принимает значение 1.

Для оценки списка переменных в каждой выбранной строке построим ассоциированную с ней элементарную конъюнкцию. Составим дизъюнкцию всех элементарных конъюнкций. Полученная формула будет искомой.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)