1 - Булевы функции. Булевы алгебры. Булевы функции. ДНФ и КНФ. Критерий Поста. Минимизация ДНФ (1059972), страница 7
Текст из файла (страница 7)
Такая операция выполняется до тех пор, покаудается получать новые импликанты вида K1 K2 . После завершения первого этапа выполняетсяоперация поглощения согласно формуле K1 K2 + K2 = K2 .K1 = 0∗∗1,ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓÔÍ-12ÌÃÒÓ17P̂ = K4 + K5 . Добавив к каждому слагаемому элементарную конъюнкцию K1 K2 K3 , описывающую ядро, получим полную функцию Патрика. #Таблица 1.7ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-120000 0001 0010 0100 0101 0111 1000 10100∗0∗1111∗0∗0111101∗111ÔÍ-12ÔÍ-12Ядро данной функции можно получить с помощью таблицы Квайна, в которой каждаястрока соответствует одной простой импликанте, а каждый столбец — одной вершине уровняединицы функции.
В каждой клетке указывается 1, если импликанта накрывает вершину,и пробел в противном случае Например, составим таблицу Квайна функции, представленнойкартой Карно на рис. 1.3 (табл. 1.7). Чтобы определить ядро функции, необходимо выявитьстолбцы, в которых находится только одна единица, и пометить соответствующие строки.
Импликанты, соответствующие помеченным строкам, образуют ядро. Например, в табл. 1.7 поодной единице содержится в столбцах, отвечающих вершинам 0001, 0010, 0100, 0111, 1000, 1010(эти единицы выделены полужирным шрифтом). Поскольку в каждой строке содержится хотябы одна выделенная единица, все простые импликанты ядровые, т.е. рассматриваемая функцияимеет единственную тупиковую ДНФ.ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÌÃÒÓ3. Исчисление высказываний3.1. Введение .
. . . . . . . . . . . .3.2. Основные положения теории N3.3. Правила естественного вывода3.4. Глобальные свойства теории N....2323242530.......35353639424447495. Исчисление предикатов5.1. Построение теории P . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . .5.2. Правила естественного вывода . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.3. Глобальные свойства теории P . . . . . . . . . . . . . . . . . . . . . . . . . . . . .515152546. Алгоритмы на графах6.1. Введение . . . . . . . . .
. . . . . . .6.2. Деревья . . . . . . . . . . . . . . . . .6.3. Остов графа наименьшего веса . . .6.4. Задача о путях в размеченном графе6.5. Циклы, разрезы и задача Эйлера . .555557606266...............................................................................4. Алгебра предикатов4.1. Предикаты и кванторы . . .
. . . . . . . .4.2. Логико-математические языки . . . . . . .4.3. Переименования и подстановки . . . . . .4.4. Семантика логико-математического языка4.5. Логические законы . . . . . . . . . . . . .4.6. Замены . . . . . . . . . . . . . . . . . . . .4.7. Упрощение формул . . . . . . . . . . . . .........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ÔÍ-12ÔÍ-12..........ÌÃÒÓ18181921.....ÔÍ-122.
Логика высказываний2.1. Алгебра высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2. Тавтологии и эквивалентность формул . . . . . . . . . . . . . . . . . . . . . . . . .2.3. Способы получения эквивалентных формул . . . . . . . . . . . . . . . . . . . . .
......ÌÃÒÓ.....11291112ÔÍ-1273ÌÃÒÓÔÍ-121. Булевы функции1.1. Булевы алгебры . .1.2. Булевы функции . .1.3. ДНФ и КНФ . . . .1.4. Критерий Поста . .1.5. Минимизация ДНФÔÍ-12ÌÃÒÓОГЛАВЛЕНИЕÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
