Математическая логика и теория алгоритмов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Математическая логика и теория алгоритмов, слайд №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

Математическая логика и теория алгоритмов, слайд №31

Математическая логика и теория алгоритмов, слайд №32

Математическая логика и теория алгоритмов, слайд №33

Математическая логика и теория алгоритмов, слайд №34

Математическая логика и теория алгоритмов, слайд №35

Математическая логика и теория алгоритмов, слайд №36

Математическая логика и теория алгоритмов, слайд №37

Математическая логика и теория алгоритмов, слайд №38

Математическая логика и теория алгоритмов, слайд №39

Математическая логика и теория алгоритмов, слайд №40

Математическая логика и теория алгоритмов, слайд №41

Математическая логика и теория алгоритмов, слайд №42

Математическая логика и теория алгоритмов, слайд №43

Математическая логика и теория алгоритмов, слайд №44

Математическая логика и теория алгоритмов, слайд №45

Математическая логика и теория алгоритмов, слайд №46

Математическая логика и теория алгоритмов, слайд №47

Математическая логика и теория алгоритмов, слайд №48

Математическая логика и теория алгоритмов, слайд №49

Математическая логика и теория алгоритмов, слайд №50

Математическая логика и теория алгоритмов, слайд №51

Математическая логика и теория алгоритмов, слайд №52

Математическая логика и теория алгоритмов, слайд №53

Математическая логика и теория алгоритмов, слайд №54

Математическая логика и теория алгоритмов, слайд №55

Математическая логика и теория алгоритмов, слайд №56

Математическая логика и теория алгоритмов, слайд №57

Математическая логика и теория алгоритмов, слайд №58

Математическая логика и теория алгоритмов, слайд №59

Математическая логика и теория алгоритмов, слайд №60

Математическая логика и теория алгоритмов, слайд №61

Математическая логика и теория алгоритмов, слайд №62

Математическая логика и теория алгоритмов, слайд №63

Математическая логика и теория алгоритмов, слайд №64

Математическая логика и теория алгоритмов, слайд №65

Математическая логика и теория алгоритмов, слайд №66

Математическая логика и теория алгоритмов, слайд №67

Математическая логика и теория алгоритмов, слайд №68

Математическая логика и теория алгоритмов, слайд №69

Математическая логика и теория алгоритмов, слайд №70

Математическая логика и теория алгоритмов, слайд №71

Математическая логика и теория алгоритмов, слайд №72

Математическая логика и теория алгоритмов, слайд №73

Математическая логика и теория алгоритмов, слайд №74

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Математическая логика и теория алгоритмов. Доклад-сообщение содержит 74 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 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. Формула , принимающая ложное значение при любых комбинациях значений входящих в нее высказываний, называются тождественно ложной (ТЛФ) и записывается .

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

Рассмотрим пример: Составить таблицу истинности для сложного высказывания Выполним сначала разметку заданной формулы. В результате получим: Так как простых высказываний 3, то число строк в таблице истинности будет , и число столбцов тоже будет .

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

I. Аксиомы одиночных элементов: I. Аксиомы одиночных элементов: 1) ; 2) 3) ; 4) . II. Аксиомы и законы отрицания: 1) ; 2) (закон противоречия); 3) (закон исключенного третьего); 4) ; 5) (законы де Моргана). III. Комбинационные законы: 1) (общий случай ); 2) (общий случай ); - переместительные законы

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

Слайд 22

Описание слайда:

Слайд 23

Описание слайда:

Алгебраические преобразования исходной формулы можно выполнять тремя способами: Алгебраические преобразования исходной формулы можно выполнять тремя способами: 1) от начала к концу, т.е. сначала выполнять наиболее приоритетные операции, двигаясь к менее приоритетным; 2) от конца к началу, т.е. двигаясь от менее приоритетных к более приоритетным операциям; 3) комбинируя предыдущие два способа.

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

В формуле обозначим , В формуле обозначим , и будем выполнять операцию импликации над А и В: Снимем отрицание, применяя закон де Моргана, и получим формулу Снимая групповое отрицание получим формулу: Применяя операцию конъюнкции к скобке, получим: Используя аксиомы , получим формулу:

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

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

Слайд 34

Описание слайда:

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

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

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

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

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

Слайд 40

Описание слайда:

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

Слайд 41

Описание слайда:

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

Слайд 42

Описание слайда:

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

Слайд 43

Описание слайда:

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

Слайд 44

Описание слайда:

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

Слайд 45

Описание слайда:

Пример: Минимизировать функцию Пример: Минимизировать функцию 1. Выполняя склеивание, получим сНД(К)Ф: 2.Удаляем избыточные импликанты : на наборе так как , то импликанта - избыточная; на наборе ; , а так как , то импликанта не является избыточной, на наборе , а так как , то не является избыточной. Таким образом, отбросив избыточную импликанту, получим ТНДФ: Таким образом, отбросив избыточную импликанту, получим ТНДФ: 3. Дальнейшему упрощению функция не поддается.

Слайд 46

Описание слайда:

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

Слайд 47

Описание слайда:

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

Слайд 48

Описание слайда:

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

Слайд 49

Описание слайда:

Для пяти переменных необходимо иметь КК с 32 клетками. Эти 32 клетки можно представить как 2 карты по 16 клеток или одну карту на 32 клетки. Одна карта на 32 клетки будет иметь такую нумерацию строк и столбцов с учетом использования отраженных кодов, которая показана на рисунке: Для пяти переменных необходимо иметь КК с 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: Минимизировать логическую функцию Пример 1: Минимизировать логическую функцию с помощью КК. Минимизируемая функция будет состоять из трех переменных, соответствующая ей КК будет состоять поэтому из 8 клеток. покрытие 1 покрытие 2

Слайд 53

Описание слайда:

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

Слайд 54

Описание слайда:

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

Слайд 55

Описание слайда:

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

Слайд 56

Описание слайда:

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