Примечание: Еще нашел таблицы. Это логические таблицы истинности.

Конъюнкция

Дизъюнкция

Пример нахождения СКНФ

Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности статьи минимизация логических функций методом Квайна:

0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

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

Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:

·

·

·

·

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так:

Остальные члены СКНФ составляются по аналогии.

Билет №11. Минимизация булевых функций в классе ДНФ. Минимизирующие карты.

Минимальная ДНФ -дизъюнктивная нормальная форма, которая содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей ДНФ.

Минимизация в классе ДНФ – процесс нахождения минимальной ДНФ.

Строить минимальные ДНФ из СДНФ можно разными способами, например, используя тождественные преобразования. Но этот процесс оказывается слишком трудоемким, так как приходиться перебирать все возможные способы применения основных законов алгебры логики к исходной формуле. Более же эффективным способом является метод минимизирующих карт.

Способ минимизации ДНФ методом минимизирующих карт.

1. Вычеркнем из таблицы(мин. карты) все строки , в которых конъюнкция последнего столбца не входит в СДНФ функции f.

2. Конъюнкции «вычеркнутых строк» вычеркнем во всех остальных строках таблицы.

3. Если в строке остались конъюнкции с различным числом сомножителей , то конъюнкции не с минимальным числом оставляем только тогда , когда они встречаются в других строках.

4. Отметим конъюнкции, оставшиеся единственными на строке. Вычеркнем строки, в которых присутствуют такие же конъюнкции.

5. Всеми возможными способами выберем из каждой строки по одной конъюнкции (из оставшихся) и составим для каждого случая ДНФ.

6. Из всех построенных ДНФ выберем минимальную. Заметим , что мы должны выполнить перебор различных ДНФ для нахождения минимальной из них. Однако в данном случае число вариантов перебора, как правило, существенно меньше вариантов перебора равносильных ДНФ или способов сокращения СДНФ.

Стр в учебнике 187-189

Билет № 12. Логические схемы. Сумматор. RS-триггер.

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

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

Логический элемент «И» (конъюнктор) реализует операцию логического умножения. (а)

Логический элемент «ИЛИ» (дизъюнктор) реализует операцию логического сложения. (б)

Логический элемент «НЕ» (инвертор) реализует операцию отрицания. (в)

Так же есть логические элементы

«И-НЕ» - штрих Шеффера «ИЛИ-НЕ» - стрелка Пирса.

Сумматор – электронная логическая схема, выполняющая полное суммирование двоичных кодов.

Триггер – логический элемент, способный хранить один разряд двоичного числа.

Вопрос 13. Понятие алгоритма. Свойства алгоритмов. Сложность строгого определения алгоритма. Машина Тьюринга как уточнение понятия алгоритма.

Свойства:

Теория по машине Тьюринга.

В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.