Презентация на тему Математическая логика и теория алгоритмов

Презентация на тему Математическая логика и теория алгоритмов, предмет презентации: Математика. Этот материал содержит 74 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

Математическая логика и теория алгоритмов


Курс лекций



Слайд 2
Текст слайда:

1. Алгебра логики 1.1. Понятие о простом и сложном высказывании


Основным понятием математической логики является простое логическое высказывание.

Под логическим высказыванием понимают всякое повествовательное предложение, утверждающее что-либо о чем-либо и принимающее истинное (И) или ложное (Л) значение в данных условиях места и времени

Иногда в определении простого высказывания опускают слова “в данных условиях места и времени”.

Дело в том, что одно и то же высказывание в разных местах (Земли, континента, страны, города и т.п.), а также в разные интервалы времени может принимать различные логические значения.



Слайд 3
Текст слайда:


Пример:

Высказывание: “Сборная команда СССР по баскетболу – лучшая в мире” для одних промежутков времени является истинным, а для других − ложным. С 1974 по 1978 г. она была чемпионом мира, поэтому приведенное высказывание было истинным, если его рассматривать относительно указанного промежутка времени, и ложным − для других промежутков времени, т.е. тех, когда она не становилась чемпионом мира.

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


Слайд 4
Текст слайда:

Существуют, однако, высказывания, которые всегда и везде являются истинными или ложными (вечные истины).

Пример:
Высказывание “5 меньше 10” является всегда и везде истинным, поэтому для такого высказывания условия места и времени можно не учитывать.
Все простые высказывания, когда они объединяются грамматическими связками “И”, “ИЛИ”, “если, то…” и др., дают новые сложные высказывания.
Пример:
Высказывание “Если число иррационально, то тоже иррационально” получается связыванием двух простых высказываний сложным союзом “если…, то…”.
Простые высказывания в дальнейшем будем обозначать малыми буквами латинского алфавита:
или буквами с индексами: Истинное значение высказывания будем обозначать цифрой “1”, а ложное − цифрой “0”.






Слайд 5
Текст слайда:

1.2. Логические операции над высказываниями

Над высказываниями, обозначенными соответствующими буквами, можно выполнять логические операции аналогично тому, как выполняются операции сложения, вычитания, умножения и деления над числами в арифметике или над буквами в алгебре.

Такими операциями в алгебре логики принято считать: отрицание (инверсия), конъюнкцию (от лат. conjunctio – союз, связь; логическое умножение), дизъюнкцию (от лат. disjunctio – различие, разделение; логическое сложение), импликацию (от лат.implico – тесная связь), и эквиваленцию (от лат. aequivalens – равносильный, равноценный).


Слайд 6
Текст слайда:

Отрицанием (инверсией) называется высказывание которое является истинным, если высказывание ложно, и ложным если высказывание истинно. Высказывание читается как “не ” или “неверно, что ”.












Таблица истинности для инверсии х ( ) :


Слайд 7
Текст слайда:

Конъюнкцией двух высказываний называется новое высказывание, которое считается истинным, если оба высказывания и истинны, и ложным, если хотя бы одно из них ложно.
Конъюнкция высказываний обозначается & , или ,
или или и читается “ и ”.










Из определения операций конъюнкции и отрицания ясно, что высказывание & всегда ложно.









Таблица истинности для конъюнкции:


Слайд 8
Текст слайда:




Дизъюнкцией двух высказываний , называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний , истинно, и ложным, если они оба ложны. Дизъюнкция обозначается или и читается “ или ”.



Из определения операции дизъюнкции и отрицания ясно, что высказывание всегда истинно.


Таблица истинност для дизъюнкции:


Слайд 9
Текст слайда:











Таблица истинности для импликации:


Слайд 10
Текст слайда:

Эквиваленцией (эквивалентностью) двух высказываний называется новое высказывание , которое считается истинным, когда оба высказывания либо одновременно истинны, либо одновременно ложны, и ложным – во всех остальных случаях.
Эквиваленция высказываний обозначается и читается
“для того, чтобы необходимо и достаточно, чтобы ”, или “ тогда и только тогда , когда ”. Эквиваленцию двух высказываний называют
еще биусловным высказыванием (т.е. двойным условным высказыванием).










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







Таблица истинности для эквиваленции:


Слайд 11
Текст слайда:

1.3.Формулы алгебры логики

Определение 2. Формула , принимающая ложное значение при любых комбинациях значений входящих в нее высказываний, называются тождественно ложной (ТЛФ) и записывается .








Всякое сложное высказывание, которое получается из простых путем применения приведенных выше операций, называется формулой алгебры логики. Для сокращения записей будем (когда это необходимо) обозначать формулы большими буквами латинского алфавита: и т.д.

Определение 1. Формула , принимающая истинное значение при любых комбинациях значений входящих в нее высказываний, называется тождественно истинной (ТИФ) или тавтологией и записывается

Например: - ТИФ, - ТЛФ.




Слайд 12
Текст слайда:

Определение 3. Две формулы и алгебры логики называются равносильными, если они принимают одинаковые логические значения при всех комбинациях логических значений входящих в них высказываний. Равносильность, как и тождественность, обозначают знаком “ ”








Например, построив таблицу истинности для высказываний и . можно убедиться, что они являются равносильными формулами (т.е. последние столбцы для первой и второй формул будут одинаковыми), т.е.
Логическое значение формулы, т.е. истинна она или ложна, зависит не только от логических значений входящих в нее высказываний, но и от очередности выполнения входящих в нее операций.
Очередность выполнения операций в формулах, как и в элементарной алгебре, устанавливается с помощью скобок.
При записи формул можно уменьшить число используемых пар скобок и тем самым несколько упростить запись формул. Для этого вводятся соглашения о приоритете одних операций над другими.




Слайд 13
Текст слайда:

1. Операция отрицания является наиболее приоритетной среди других операций. Поэтому можно не заключать в скобки формулу или часть её, стоящую под знаком отрицания. Тогда вместо записи ( можно писать .
2. Считается, что знак операции конъюнкции связывает высказывания формулы “сильнее” знаков т.е. вместо пишем , , вместо пишем ,и вместо . пишем .
3. Считается, что знак связывает высказывания сильнее, чем знаки и , т.е. вместо можно писать , а вместо . можно писать .
4. Считается, что знак сильнее связывает высказывания, чем знак , т.е. вместо пишем .
5. Можно опускать внешние скобки, которые содержат внутри себя остальные символы, составляющие формулу. Так, формулу
можно писать .




















Эти соглашения следующие:



Слайд 14
Текст слайда:

Приведенные соглашения значительно упрощают запись формулы. Так, например, формула , записанная с учетом сказанного выше, будет выглядеть так :




Расстановку цифр над операциями в формуле, обозначающих последовательность их выполнения, назовем разметкой формулы.
Введенные соглашения и разметка исходной формулы очень помогает при составлении таблиц истинности. Приведем порядок составления таблиц истинности сложного высказывания. Сначала нужно определить приоритеты выполнения операций. Затем, исходя из количества простых высказываний, входящих в сложное высказывание, выписывают всевозможные комбинации логических значений этих высказываний. Количество комбинаций определяет число строк таблицы истинности, и для двоичных комбинаций оно равно , где – число различных простых высказываний.
Количество столбцов таблицы истинности определяется суммой чисел последовательно выполняемых операций и простых высказываний.






Слайд 15
Текст слайда:


Рассмотрим пример:






Составить таблицу истинности для сложного высказывания

Выполним сначала разметку заданной формулы.

В результате получим:

Так как простых высказываний 3, то число строк в таблице истинности будет , и число столбцов тоже будет .




Слайд 16
Текст слайда:







Таблица истинности для формулы :



Слайд 17
Текст слайда:

1.4. Аксиомы и законы алгебры логики

Как и любая точная наука, алгебра логики опирается на некоторые аксиомы и законы, позволяющие доказывать равносильность
формул, упрощать формулы и приводить их к заданному виду, не
прибегая к построению таблиц истинности. Это практически всегда
дает более короткий и менее громоздкий путь, чем построение
таблиц истинности.

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


Слайд 18
Текст слайда:

I. Аксиомы одиночных элементов:
1) ; 2)
3) ; 4) .

II. Аксиомы и законы отрицания:
1) ; 2) (закон противоречия);
3) (закон исключенного третьего);
4) ; 5) (законы де Моргана).

III. Комбинационные законы:
1) (общий случай );
2) (общий случай );

- переместительные законы
















– законы
идемпотентности

– сочетательные
законы.


Слайд 19
Текст слайда:

7) – распределительный
(дистрибутивный) закон первого рода;

8) – распределительный
(дистрибутивный) закон второго рода.




Пример:
Возьмем правую часть закона 8) и выполним логическое
перемножение скобок:



Слайд 20
Текст слайда:

IV. Некоторые важные равносильности:
1) ; 2) ;

3) ; 4) .





V. Закон двойственности.
Пусть формула содержит только операции конъюнкции, дизъюнкции и отрицания. Операцию конъюнкции называют двойственной операции дизъюнкции, и наоборот.

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

Например:







Слайд 21
Текст слайда:







Свойства операций импликации и эквивалентности, вытекающие из приведенных выше равносильностей, следующие:

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

Действительно: Отсюда видим, что .

2. Операция импликации не обладает сочетательным свойством (законом).

Действительно: ,

, ,
.












Слайд 22
Текст слайда:

3. Операция эквивалентности обладает переместительным свойством.

Действительно, на основании равносильностей IV.2 и IV.1 имеем:



4. Операция эквивалентности обладает сочетательным свойством.

Действительно, построив таблицы истинности или выполнив соответствующие преобразования, можно показать, что выполняются равносильности:



Слайд 23
Текст слайда:

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



1) от начала к концу, т.е. сначала выполнять наиболее приоритетные операции, двигаясь к менее приоритетным;

2) от конца к началу, т.е. двигаясь от менее приоритетных к более приоритетным операциям;

3) комбинируя предыдущие два способа.




Слайд 24
Текст слайда:

Приведём пример упрощения формулы, используя прямой порядок выполнения операций:



Используя правило поглощения , получаем формулу:


Выполняя операцию с номером 5, будем иметь
Остается выполнить операцию отрицания. Выполнив её,
используя закон де Моргана, получим формулу







Слайд 25
Текст слайда:

В формуле обозначим ,
и будем выполнять операцию импликации над А и В:


Снимем отрицание, применяя закон де Моргана, и получим формулу

Снимая групповое отрицание получим формулу:

Применяя операцию конъюнкции к скобке, получим:

Используя аксиомы ,
получим формулу:

Приведём последовательное упрощение той же формулы, используя обратный порядок выполнения операций.














Слайд 26
Текст слайда:

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

Сведем правую формулу приведенной равносильности к формуле, содержащей только операции
К формуле применим аксиому . Тогда:




Таким образом, если говорят об упрощении формулы, то имеют в виду ее сведение к ФПСО.

Если любую формулу алгебры логики можно свести к некоторой другой равносильной формуле, содержащей только определенную систему операций, то такая система операций называется функционально полной системой операций (ФПСО) или базисной. В алгебре логики такой ФПСО являются системы операций:









Слайд 27
Текст слайда:

1.4.1. Правила склеивания для элементарных конъюнкций и дизъюнкций

Логическое произведение/сумма любого числа высказываний называется элементарным, если сомножители/слагаемые в нем являются либо одиночными высказываниями, либо их отрицаниями
Например: – элементарное произведение,
– неэлементарное произведение.

Количество сомножителей в элементарном произведении называется его рангом.



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


Слайд 28
Текст слайда:


Правило склеивания для элементарных конъюнкций:

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

Пример:

Правило склеивания для элементарных дизъюнкций:


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

Пример:




Слайд 29
Текст слайда:

1.4.2. Правила поглощения для элементарных конъюнкций и дизъюнкций


Правило поглощения для элементарных конъюнкций:

Логическую сумму двух элементарных конъюнкций разных рангов, из которых одна является частью другой, можно заменить слагаемым, имеющим меньший ранг.
Пример:


Правило поглощения для элементарных дизъюнкций:

логическое произведение двух элементарных дизъюнкций разных рангов, одна из которых является частью другой, можно заменить сомножителем меньшего ранга.
Пример:
Правила склеивания и поглощения, как не трудно заметить, являются следствиями распределительных знаков.



Слайд 30
Текст слайда:

1.4.3. Правило развёртывания


Это правило также является следствием распределительных
законов и регламентирует действие, обратное склеиванию. Оно
используется, когда нужно составить некоторое логическое
выражение в виде совокупности конституент единицы (КЕ) или
конституент (КН) нуля.
Конституента единицы – это конъюнкция всех высказываний,
которые входят в неё в прямом или инверсном виде лишь по
одному разу и обращающаяся в ноль при одном наборе логических
значений высказываний и в единицу при всех остальных наборах.
Количество KE и КН заданного числа высказываний совпадает,
как это следует из определения, с числом различных наборов
высказываний и равно . Конституенты принято обозначать
какими-либо символами, например: и . Единица или ноль в
верхнем индексе означает вид конституенты, т.е. КЕ это или КН,
нижний индекс означает ее номер, совпадающий с номером набора.




Слайд 31
Текст слайда:

Все КЕ для двух высказываний:


Слайд 32
Текст слайда:

Все КН для двух высказываний:


Слайд 33
Текст слайда:

Развёртывание элементарных конъюнкций


1. В развертываемую элементарную конъюнкцию ранга вводятся в качестве дополнительных сомножителей единиц, где – число высказываний и
2. Каждая единица представляется в виде , где – высказывание, отсутствующее в исходной конъюнкции.
3. Производится раскрытие всех скобок на основе распределительного закона 1-го рода, что приводит к развертыванию исходной конъюнкции ранга в логическую сумму КЕ.
Пример: Развернуть конъюнкцию . Здесь
предполагается, что число высказываний , но два из них отсутствуют, тогда:
1)
2)
3)












Слайд 34
Текст слайда:

Развёртывание элементарных дизъюнкций




1. В развертываемую дизъюнкцию ранга вводится n-r нулей.
2. Каждый нуль представляется произведением ,
где – высказывание, отсутствующее в исходной дизъюнкции.
3. Полученная сумма преобразуется с помощью распределительного закона 2-го рода в логическое произведение КН.

Пример: Развернуть дизъюнкцию . Здесь число высказываний , отсутствует высказывание :








Слайд 35
Текст слайда:

1.5. Функции алгебры логики. Нормальные формы логических функций


Логическая функция [функция алгебры логики (ФАЛ)]
– это выражение, представляющее собой сложное высказывание, состоящее из нескольких простых высказываний , связанных соединительными словами. Это сложное высказывание принимает значения 0 или 1 на всех наборах логических значений всех простых высказываний.




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



Слайд 36
Текст слайда:




Полностью определенная функция – это логическая функция,
принимающая значение 0 или 1 на всех входных наборах.

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

Частично определенную логическую функцию можно сделать
полностью определенной, приписав безразличным наборам
произвольные значения: 0 или 1.


Слайд 37
Текст слайда:

В алгебре логики каноническими принято считать нормальную дизъюнктивную форму (НДФ) и нормальную конъюнктивную форму (НКФ) и соответственно совершенную НДФ (СНДФ) и совершенную НКФ (СНКФ).

НДФ – это дизъюнкция нескольких элементарных конъюнкций.

СНДФ – форма, все члены которой имеют высший ранг, являясь
конституентами единицы или нуля

Общая запись любой логической функции в СНДФ имеет вид:




Иначе говоря, значение определяет факт вхождения в .
При конституента входит в , а при – не входит.








Слайд 38
Текст слайда:

Пример: По заданной таблице истинности составить СНДФ функций



Общая запись любой логической функции в СНКФ имеет вид:




Иначе говоря, в СНКФ будет отсутствовать тот дизъюнктивный член, для которого .



Слайд 39
Текст слайда:

СНКФ для выше приведенной таблицы истинности будут иметь
вид :



В общем случае переход к СНДФ и СНКФ осуществляется за три
шага.

1. Путем многократного применения закона отрицания снимаются групповые и общие отрицания так, чтобы они оставались только у одиночных переменных.
2. С помощью распределительных законов производится переход к одной из нормальных форм функций:
а) для перехода к НДФ применяется распределительный закон первого
рода [раскрываются скобки, т.е. ];
б) для перехода к НКФ применяется распределительный закон второго
рода [вводятся скобки, т.е ;
3. С помощью правила развертывания производится преобразование членов НДФ или НКФ в соответствующие конституенты.




Слайд 40
Текст слайда:

Пример: Преобразовать функцию
в СНДФ и СНКФ.


1. Применяя законы инверсии, снимаем все групповые отрицания:


2. Применяя распределительный закон 1-го рода, получаем:



Применяя распределительный закон 2-го рода к формуле, полученной после первого шага, будем иметь:









Слайд 41
Текст слайда:

3. Применяя правило развертывания, переходим от НДФ к СНДФ и от НКФ к СНКФ:



Переход от одной формы логической функции к другой можно осуществить, используя таблицу истинности. Для этого надо по заданной формуле построить таблицу истинности. Для в всех 1 в столбце функции составить КЕ, соединив их знаком . Для всех 0 в столбце функции составить КН, заключив их в скобки и поставив между ними знак .


Слайд 42
Текст слайда:

1.6.Минимизация логических функций

К настоящему времени разработано достаточно большое число методов и приемов минимизации логических функций. Наиболее известными и распространенными среди них являются:

1) расчетный метод – метод непосредственных логических
преобразований;

2) табличный метод – метод карт Карно или Вейча – Карно;

3) расчетно-табличный метод Квайна.


Слайд 43
Текст слайда:

Исходной формой для любого из этих методов является одна из совершенных нормальных форм СНДФ или СНКФ. В общем случае любой из упомянутых методов состоит из трех этапов:

1. Переход от СНД(К)Ф к сокращенной сНД(К)Ф путем
выполнения всех возможных склеиваний друг с другом сначала
конституент, а затем всех членов сумм (произведений) более
низкого ранга до тех пор, пока склеивание возможно.

2. Переход от сНД(К)Ф к тупиковой нормальной
дизъюнктивной (конъюнктивной) форме (ТНД(К)Ф) путем
устранения избыточных импликант.

3. Переход от ТНД(К)Ф к минимальной форме (МНД(К)Ф) логической функции.


Слайд 44
Текст слайда:

1.6.1. Расчетный метод минимизации



Каждый из конкретных методов минимизации состоит из тех же трех шагов, что указывалось выше. Но эти шаги в каждом методе могут иметь свою особенность:
1.Склеивание всевозможных членов исходной СНД(К)Ф, т.е.
сначала конституент, затем импликант ранга n - 1 и т.д., пока
склеивание возможно.

2.Проверка каждой простой импликанты в СНД(К)Ф на избыточность с целью её удаления.

3. Упрощение полученной ТНД(К)Ф путем применения операции
отрицания и распределительного закона 1-го или 2-го рода.


Слайд 45
Текст слайда:

Пример: Минимизировать функцию



1. Выполняя склеивание, получим сНД(К)Ф:


2.Удаляем избыточные импликанты : на наборе
так как , то импликанта - избыточная;
на наборе ; , а так как ,
то импликанта не является избыточной, на наборе , а так как , то
не является избыточной.
Таким образом, отбросив избыточную импликанту, получим ТНДФ:

Таким образом, отбросив избыточную импликанту, получим ТНДФ:


3. Дальнейшему упрощению функция не поддается.


Слайд 46
Текст слайда:

1.6.2. Табличный метод минимизации


В этом методе два первых шага как бы объединены и выполняются с помощью специальной таблицы, называемой картой Карно (КК) или картой Карно-Вейча (еще иногда называемой диаграммой). Третий шаг выполняется так же, как и в расчетном методе.

Карта Карно для двух переменных :


Слайд 47
Текст слайда:

Следует отметить особенность нумерации клеток. Их нужно
нумеровать так, чтобы две рядом расположенные клетки
отличались значением всего лишь одного разряда.
Процесс получения отраженных кодов (код Грэя) мы можем представить
так :

Карта Карно для 3 – х переменных:


Слайд 48
Текст слайда:

Для 3-разрядных двоичных чисел двоичный отраженный код формируется следующим образом:





Для четырех переменных КК содержит 16 клеток


Слайд 49
Текст слайда:

Для пяти переменных необходимо иметь КК с 32 клетками. Эти 32 клетки можно представить как 2 карты по 16 клеток или одну карту на 32 клетки. Одна карта на 32 клетки будет иметь такую нумерацию строк и столбцов с учетом использования отраженных кодов, которая показана на рисунке:











В карте Карно, изображенной на рис.6, нумерация клеток дается в десятичной системе счисления. Это позволяет производить очень компактную запись логической функции


Слайд 50
Текст слайда:


Если логическая функция записана в виде
то это значит, что число клеток будет
,
т.е. число переменных будет 4, число клеток будет
а единицы надо поместить в клетки с номерами 0,1,3,4,6,9,11.
В двоичной системе счисления эти номера будут иметь вид:
0000,0001,0011,0100,0110,1001,1011.
Тогда КК с отображенной на нее приведенной функцией будет
иметь вид:


Пример:


Слайд 51
Текст слайда:

Правила минимизации с помощью карт Карно

1. соседних клеток, содержащих 1, и расположенных по
вертикали либо по горизонтали в виде прямоугольника либо
квадрата (такую совокупность клеток называют покрытием),
соответствуют одной импликанте, ранг которой где
− число переменных, меньше ранга покрываемых конституент
на единиц. Чем больше клеток в покрытии, тем проще
выражаемый этим покрытием член логической функции −
импликанта.
2. Импликанта, соответствующая некоторому покрытию
заполненных единицами клеток, содержит символы тех
переменных, значения которых совпадают у всех клеток,
образующих покрытие. Причем символ берется с отрицанием,
если для всех клеток покрытия он принимает значение 0, и без
отрицания – в противном случае.


Слайд 52
Текст слайда:

Пример 1: Минимизировать логическую функцию
с помощью КК. Минимизируемая функция будет состоять из трех
переменных, соответствующая ей КК будет состоять поэтому из 8 клеток.


покрытие 1 покрытие 2


Слайд 53
Текст слайда:



Следует отметить некоторые особенности работы с покрытиями. Каждое покрытие нужно использовать только один раз. Если КК свернуть в цилиндр вдоль горизонтальной или вертикальной оси, то будет видно, что крайние клетки тоже оказываются соседними и они могут образовывать покрытие.



Слайд 54
Текст слайда:

Пример 2:
КК с отображенной на нее логической функцией, когда единицы
находятся в крайних клетках. Эта функция имеет вид










Результат минимизации:


Слайд 55
Текст слайда:

Минимизация этим методом отличается от расчетного только способом выявления избыточных членов в сНДФ. Данный метод предложен американским ученым Квайном, и поэтому называется его именем. Его удобно рассматривать в виде алгоритма с комментариями. Считаем, что минимизируемая логическая функция приведена к СНДФ.
Переход от СНДФ к сНДФ. Отыскиваются все простые импликанты. Для этого выписываются все конституенты и все их пары исследуются на возможность склеивания друг с другом. Конституенты, участвующие хотя бы в одном склеивании, отмечаются, но не исключаются из дальнейших сравнений. В результате выявляются импликанты, содержащие по (n-1)-й переменной. С полученными импликантами выполняется та же процедура, что и с исходными конституентами. В результате выявляются импликанты, содержащие n-2 переменные, и так продолжается до тех пор, пока членов, допускающих склеивание, не останется. Все не отмеченные в процессе указанного преобразования члены представляют собой простые импликанты.

1.6.3. Расчётно-табличный метод минимизации (метод Квайна)


Слайд 56
Текст слайда:

Переход от сНДФ к ТНДФ. Дизъюнкция всех простых импликант может содержать избыточные импликанты. Поэтому их надо исключить. Для этого составляется импликантная таблица, строки которой обозначаются выявленными на 1-м шаге простыми импликантами, а столбцы – конституентами, входящими в СНДФ исходной функции.
Расстановка меток. Любая клетка импликантной таблицы отмечается, например, цифрой 1, если она попадает на пересечение конституенты и импликанты, полностью входящей в конституенту. В каждом столбце при этом может оказаться по нескольку отмеченных клеток. Задача упрощения НДФ сводится к вычеркиванию из таблицы максимального количества строк таким образом, чтобы после этого в каждом столбце осталась, по крайней мере, одна отмеченная клетка.


Слайд 57
Текст слайда:

Выделение ядра Квайна (существенных импликант). Выявляются и вычеркиваются столбцы, содержащие только по одной отмеченной клетке. Простые импликанты, соответствующие этим клеткам, вносятся в окончательное выражение НДФ как обязательные члены. Если таких столбцов нет, то переход к п.5, если же есть, то в таблице зачеркиваются строки, соответствующие обязательным простым импликантам и столбцы, содержащие отмеченные клетки в вычеркнутых строках.
Поглощение (сжатие) столбцов. Если после этого в таблице окажутся такие пары столбцов, что все отмеченные клетки i-го столбца совпадают полностью или частично с клетками j-го столбца, то j-й столбец вычеркивается. Если таких пар столбцов нет, то переход к п.7, иначе – к п.6.
Вычеркивание пустых строк. Строки, не содержащие после выполнения п.п. 4 и 5 ни одной отмеченной клетки, также вычеркиваются.


Слайд 58
Текст слайда:

Поглощение (сжатие) строк. Если в таблице имеется такая пара строк, что все отмеченные клетки k-й строки совпадают полностью или частично с отмеченными клетками l-й строки, то k-я строка вычеркивается. Если таких строк нет, то переход к п.8
Получение МНДФ. Для этого импликанты ядра Квайна, т.е. полученные в п. 4 и оставшиеся не вычеркнутыми после выполнения п. 7, соединяются знаками дизъюнкции.
Пример:
Минимизировать логическую функцию четырех переменных, заданную в числовой форме . Так как наша цель – рассмотрение процесса преобразования импликантной таблицы, то п. 10 алгоритма выполнять не будем, а выпишем готовые импликанты. Их совокупность будет иметь вид

Прочерки в импликантах указывают на отсутствие в них соответствующей переменной.


Слайд 59
Текст слайда:

В табл. 9 вертикальные и горизонтальные линии, пересекающие соответствующие столбцы и строки, пронумерованы цифрами. Эти цифры указывают на порядок вычеркивания столбцов и строк.
В соответствии с п.4 алгоритма устанавливаем, что импликанты 0–0– и –0–0 являются существенным для конституент
0000,0001,0100,0101 и 0000, 0010,1000,1010. Они должны быть внесены в МНДФ. Поэтому вместе со 2-м и 3-м столбцами, как содержащими всего по одной отмеченной клетке, вычеркиваем 4-ю и 5-ю строки, а также столбцы 1,4,5,7 и 8, на пересечении с которыми в вычеркнутых строках 4 и 5 стоят единицы.


Слайд 60
Текст слайда:

В результате выполнения этих операций импликантная таблица приобретает вид:











Далее выполняем поглощение столбцов. Однако это невозможно, так как в таблице нет ни одной пары столбцов, которые бы полностью или частично совпадали. Поэтому в соответствии с п.7 алгоритма выполняем поглощение строк. Видим, что строка 2 поглощает строку 1, а строка 5 – строку 4.


Слайд 61
Текст слайда:

В результате получаем таблицу:








Снова выполняем поглощение столбцов и получаем таблицу:


Слайд 62
Текст слайда:

Так как в предыдущей таблице получили строку, не содержащую единиц, то, вычеркивая её, получаем окончательную таблицу:







Соединяя импликанты, соответствующие столбцам с одной отмеченной клеткой и оставшиеся в последней таблице, знаком , получим МНДФ:


Достоинством рассмотренного метода Квайна является то, что он применим для любого числа переменных и может быть реализован в виде программы для ЭВМ.
В качестве недостатка можно отметить его относительную сложность.



Слайд 63
Текст слайда:

1.7 Некоторые применения алгебры логики


Слайд 64

Слайд 65

Слайд 66

Слайд 67
Текст слайда:




Слайд 68

Слайд 69

Слайд 70
Текст слайда:

Такая схема называется инвертором или схемой НЕ. Она инвертирует сигнал, т.е. переворачивает фазу сигнала на 180 0 (иначе говоря, если мы подадим на вход инвертора сигнала , то на его выходе появится сигнал ).

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


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


или



Слайд 71

Слайд 72
Текст слайда:

Если над некоторым числом переменных, соединенных операцией или .
выполняется операция отрицания, то начертание логических схем будет выглядеть так:

На вход логической схемы могут подаваться уже инвертированные сигналы. Тогда 3-входовые схемы И и ИЛИ будут соответственно такие:

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


Слайд 73

Слайд 74

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика