'

Решение логических задач

Понравилась презентация – покажи это...





Слайд 0

Решение логических задач


Слайд 1

Логические функции одной переменной


Слайд 2

Логические функции двух переменных


Слайд 3

Логическое умножение Коньюнкция conjunctio – лат. – связываю Соединение двух простых высказываний A и B в одно составное с помощью союза «и» (а, но) называют логическим умножением или конъюнкцией, а результат операции — логическим произведением. Указание о логическом перемножении простых высказываний A и B обозначается так: AB, A?B, A&B.


Слайд 4

Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны. Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. A•B•C=1, только если A=1, B=1, C=1.


Слайд 5

Свойства конъюнкции


Слайд 6

Логическое сложение Дизъюнкция disjunctio – лат. – различаю Соединение двух простых высказываний A и B в одно составное с помощью союза «или», употребляемого в неисключающем смысле, называется логическим сложением или дизъюнкцией, а полученное составное высказывание — логической суммой. Указание о необходимости выполнить логическое сложение высказываний A и B записывается так: A+B или A?B.


Слайд 7

Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны. Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. A+B+C=0, только если A=0, B=0, C=0.


Слайд 8

Свойства дизъюнкции


Слайд 9

Логическое отрицание Инверсия inversio – лат. – переворачиваю Присоединение частицы «не» к сказуемому данного простого высказывания A называется операцией логического отрицания или инверсией или Присоединение слов «Неверно, что …» ко всему данному высказыванию A называется операцией логического отрицания Указание выполнить логическое отрицание над высказыванием A записывается так:


Слайд 10

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна. закон двойного отрицания


Слайд 11

Логическое следование Импликация implicatio – лат. – тесно связываю Логическое следование соответствует обороту «если…, то…», обозначается A?B или A?B. Читается: если А, то В; из А следует В; А имплицирует В; А достаточно для В; В необходимо для А; А только тогда, когда В.


Слайд 12

Высказывание A?B ложно в том и только в том случае, когда условие (первое высказывание A) истинно, а следствие (второе высказывание B) ложно.


Слайд 13

Логическая равносильность Эквиваленция aequivalens – фр. – равноценное или равнозначное соответствует оборотам речи: «тогда и только тогда» «в том и только в том случае» обозначается A-B или A?B.


Слайд 14

Выражение A?B истинно в том и только в том случае, когда оба исходных высказывания одновременно истинны или одновременно ложны.


Слайд 15

Сложение по модулю «2» Соединение двух простых высказываний A и B в одно составное с помощью союза «или», употребляемого в исключающем смысле, называется строгой дизъюнкцией, сложение по модулю «2», исключающее «или». Обозначается A?B.


Слайд 16

Выражение A?B истинно в том и только в том случае, когда значения исходных высказываний не равны между собой.


Слайд 17

Закон коммутативности Переместительный закон A+B=B+A A•B=B•A


Слайд 18

Сочетательный закон Закон ассоциативности (A+B)+C=A+(B+C) (A • B) • C= A •(B • C)


Слайд 19

Распределительный закон Закон дистрибутивности (A+B)•C=(A•C)+(B•C) (A•B)+C=(A+C)•(B+C)


Слайд 20

Закон инверсии Формулы де Моргана


Слайд 21

Формулы склеивания (закон исключения)


Слайд 22

Формулы поглощения


Слайд 23


Слайд 24

1. Является ли данная функция тождественно-истинной? Способы решения: Упрощение функции Построение таблицы истинности


Слайд 25

1 способ


Слайд 26

1 2 3 4 5 2 способ


Слайд 27


Слайд 28


Слайд 29


Слайд 30


Слайд 31


Слайд 32


Слайд 33

2. Следующие два высказывания истинны: «неверно, что если магазин А организует распродажу, то магазин С тоже»; «из двух магазинов В и С организует распродажу только один». Какие магазины организуют распродажу?


Слайд 34

«Если магазин А организует распродажу, то магазин С тоже» A>C «Неверно, что если магазин А организует распродажу, то магазин С тоже» Из условия известно, что это высказывание истинно. Следовательно:


Слайд 35

«Из двух магазинов В и С организует распродажу только один»


Слайд 36

Это возможно только в одном случае, когда A=1, B=1, С=0. То есть, магазины A и B проводят распродажу, а магазин С – нет.


Слайд 37

3. На олимпиаде по информатике студенты A, B, C и D заняли первые четыре места. Когда их спросили о распределении мест, они дали три ответа: D – первый или B – второй; C – первый или A – четвертый; D – второй или B – третий. Как распределились места, если в каждом ответе только одно утверждение истинно?


Слайд 38

D – первый или B – второй: D1+B2=1 C – первый или A – четвертый: C1+A4=1 D – второй или B – третий: D2+B3=1 (D1+B2)(C1+A4)(D2+B3)=1 (D1C1+B2C1+D1A4+B2A4)(D2+B3)=1 B2C1D2+D1A4D2+B2A4D2+B2C1B3+D1A4B3+B2A4B3=1 D1A4B3=1 Следовательно, D – первый, С – второй, B – третий, A – четвертый.


Слайд 39

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


Слайд 40

«Виктор пойдет на рыбалку» - A «Будет солнечная погода» - B «Будет жарко» - C Перефразируем высказывание: «Если будет солнечная погода и не будет жарко, то Виктор пойдет на рыбалку». Тогда исходное высказывание имеет вид:


Слайд 41

Будет солнечная погода и нежарко, а Виктор не пойдет на рыбалку.


Слайд 42

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


Слайд 43

Конъюнктивно-нормальная форма КНФ — является логическим произведением элементарных дизъюнкций. Совершенная КНФ – логическое произведение элементарных дизъюнкций, в каждой из которых присутствуют все переменные данной функции.


Слайд 44

Табличный способ приведения к СДНФ Составляем таблицу истинности данной функции. Рассматриваем только те строки таблицы, в которых функция принимает значение 1. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Причем аргумент, принимающий значение 0, входит в нее с отрицанием; значение 1 – без отрицания. Наконец, образуем дизъюнкцию всех полученных конъюнкций.


Слайд 45

Табличный способ приведения к СКНФ Составляем таблицу истинности данной функции. Рассматриваем только те строки таблицы, в которых функция принимает значение 0. Каждой такой строке соответствует дизъюнкция всех аргументов (без повторений). Причем аргумент, принимающий значение 0, входит в нее без отрицания; значение 1 – с отрицанием. Наконец, образуем конъюнкцию всех полученных дизъюнкций.


Слайд 46

Если условится из двух форм, СДНФ и СКНФ, отдавать предпочтение той, которая содержит меньше букв, то СДНФ предпочтительней, если в столбце значений функции таблицы истинности меньше единиц; СКНФ – если в этом столбце меньше нулей.


Слайд 47

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


Слайд 48


Слайд 49

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


Слайд 50

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


Слайд 51


Слайд 52

Теперь по таблице истинности построим дизъюнктивно-нормальную форму. Отберем те строки в таблице истинности, которые в результате дают единицу. Для каждой строки строится конъюнкция всех переменных. Если переменная в этой строке равна нулю, то она берется с отрицанием, если единице – без отрицания. Затем соединим все полученные конъюнкции операциями дизъюнкции.


Слайд 53


Слайд 54

Стрелка Пирса (символ Лукашевича) логическая операция с двумя переменными, соответствует обороту речи «ни…, ни…», обозначается следующим образом: Выражение истинно в том и только в том случае, когда оба высказывания A и B ложны.


Слайд 55

Стрелка Пирса (символ Лукашевича)


Слайд 56

Штрих Шеффера логическая операция с двумя переменными, соответствует обороту речи «не… или не…», обозначается следующим образом Выражение A|B ложно в том и только в том случае, когда оба высказывания A и B истинны.


Слайд 57

Штрих Шеффера


Слайд 58

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


Слайд 59


Слайд 60

A B C & & & & & & ¬A ¬B ¬C ¬(A•B•¬C) ¬(A•¬B) ¬((¬(A•B•¬C))•(¬(A•¬B)))


Слайд 61

5. После традиционного вечера встречи с выпускниками школы в стенгазете появилась заметка о трех наших бывших учениках. В ней было сказано, что Иван, Андрей и Борис стали учителями. Теперь они преподают разные дисциплины: один из них – математику, второй – физику, а третий – химию. Живут они тоже в разных городах: Минске, Витебске, Харькове. В заметке было также написано, что их первоначальные планы осуществились не полностью: Иван живет не в Минске. Андрей – не в Витебске. Житель Минска преподает не математику. Андрей преподает не физику. Повезло только жителю Витебска: он преподает любимую им химию. Можно ли по этим данным определить, кто где живет и что преподает?


Слайд 62

Алгоритм решения задач на приведение множеств во взаимно-однозначное соответствие Строится пространственная система координат XYZ, на осях проставляются названия множеств и элементы этих множеств. Читается условие задачи. Если пара элементов в двух множествах находится в соответствии, то точка, лежащая на пересечении соответствующих прямых становится центром темного кружка, в противном случае – белого кружка. Применяется правило экстраполяции. Применяется правило проектирования. Повторять шаги 3)-4) пока это возможно. Если в сложившейся ситуации возможности экстраполяции и проектирования исчерпаны, а задача не решена, то делается допущение о цвете фигуры в какой-либо свободной вершине сетки. В случае противоречия допущение отклоняется цвет фигуры в данной точке меняется на противоположный.


Слайд 63

Правила экстраполяции в плоскости «Темная» экстраполяция. Если на горизонтали (вертикали) все фигуры, кроме одной, светлы, то свободная занимается темной фигурой. «Светлая» экстраполяция. Если на горизонтали (вертикали) имеется «темная» фигура, то все фигуры на ней – светлые. Множественная экстраполяция. Если две (n) параллели в плоскости одинаково светло раскрашены везде за исключением двух (n) неокрашенных вершин, то на двух (n) параллелях другого направления, проходящих через эти вершины вне данных прямых вставляются светлые фигуры.


Слайд 64

Правило множественного проектирования «Темная» фигура в своей плоскости проектируется на координатные оси. Прямые, проведенные через проекции в двух других плоскостях, раскрашиваются одинаково.


Слайд 65

Б А И М Х Ф М В Х Имена Предмет Город


Слайд 66

Иван преподает химию и живет в Витебске. Андрей преподает математику и живет в Харькове. Борис преподает физику и живет в Минске.


×

HTML:





Ссылка: