Основы логики
план-конспект урока по информатике и икт (8 класс)

Слайд 1

Слайд 2

Отцом алгебры логики по праву считается английский математик XIX столетия Джордж Буль (1815 – 1864) . В его честь алгебра логики названа булевой алгеброй высказываний Алгебра логики изучает строение (форму структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.

Слайд 3

Логическое высказывание – это повествовательное предложение, про которое однозначно можно сказать: истинно оно или ложно Будут ли высказыванием следующие предложения ? Пятью пять – двадцать пять. Пекин – столица Японии. Информатика – любимый предмет. Х+3=5 Победа! Который час? Ты сегодня пойдёшь в школу?

Слайд 4

Составное высказывание – логическая функция, которая содержит несколько простых мыслей, соединенных между собой с помощью логических операций. Символическое обозначение – F ( A , B ,…). Логические операции – логическое действие Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение, значение которого можно вычислить. Значением логического выражения могут быть только ИСТИНА (1) или ЛОЖЬ (0) .

Слайд 5

А={Луна – планета}; В={2*2=4}; Простые высказывания Любое высказывание либо истинно ( 1), либо ложно (0)

Слайд 6

А={Луна – планета}; В={2*2=4}; А или В - Луна – планета или 2*2=4; А и В - Луна – планета и 2*2=4; не А и не В - Луна не планета и 2*2не равно 4; Составные высказывания

Слайд 7

Таблицы истинности – таблицы, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных Причем, количество строк в таблице истинности вычисляется как 2 n , где n – количество переменных, а количество столбцов = количество переменных + количество логических операций.

Слайд 8

Алгоритм построения таблицы истинности N - количество переменных. M - количество операций. Число столбцов = (N+M) . Число строк =2 N .

Слайд 9

В алгебре логики логические связки и соответствующие им логические операции имеют специальные названия и обозначаются следующим образом: логическая связка название логической операции обозначения не Отрицание, инверсия ¯,┐, ¬, not и, а, но, хотя, однако Конъюнкция, логическое умножение &, ●,  , and или Дизъюнкция, нестрогая дизъюнкция, логическое сложение  , + , or либо Разделительная (строгая) дизъюнкция, исключающее ИЛИ, сложение по модулю 2  ,  , xor, M2 если…, то; А влечет В; В, если только А; только тогда А, если В; достаточным условием В является А; необходимым условием В является А. Импликация, следование  ,  Тогда и только тогда, когда… Эквивалентность, эквиваленция, равносильность, равнозначность  ,  , ~, 

Слайд 10

Конъюнкция (логическое умножение) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Таблица истинности Диаграмма Эйлера – Венна А B A&B 0 0 0 0 1 0 1 0 0 1 1 1

Слайд 11

Дизъюнкция (логическое сложение) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным, когда хотя бы одно из двух образующих его высказываний истинно Таблица истинности Диаграмма Эйлера – Венна А B A  B 0 0 0 0 1 1 1 0 1 1 1 1

Слайд 12

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

Слайд 13

Импликация (логическое следование) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно. Таблица истинности Диаграмма Эйлера – Венна А B 0 0 1 0 1 1 1 0 0 1 1 1

Слайд 14

Свойства импликации

Слайд 15

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

Слайд 16

Свойства эквивалентности:

Слайд 17

Строгая или разделительная дизъюнкция (исключающее ИЛИ, сложение по модулю 2) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда ровно одно из исходных высказываний является истинным . Таблица истинности Диаграмма Эйлера – Венна А B 0 0 0 0 1 1 1 0 1 1 1 0

Слайд 18

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

Слайд 19

Стрелка Пирса (символ Лукашевича, ИЛИ-НЕ) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба высказывания ложны. Соответствует обороту речи «ни…,ни…». Таблица истинности А B 0 0 1 0 1 0 1 0 0 1 1 0 Обозначается:

Слайд 20

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

Слайд 21

Свойства Стрелки Пирса:

Слайд 22

Штрих Шеффера (И-НЕ) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда оба высказывания истинны. Соответствует обороту речи «не…или не…». Таблица истинности А B 0 0 1 0 1 1 1 0 1 1 1 0 Обозначается:

Слайд 23

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

Слайд 24

Свойства штриха Шеффера: ; ; ; .

Слайд 25

А В 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0

Слайд 26

При составлении логического выражения необходимо учитывать порядок выполнения логических операций: Действия в скобках; Инверсия; Конъюнкция; Дизъюнкция (строгая и нестрогая); Импликация; Эквивалентность.

Слайд 27

Основные операции: и , или , не

Слайд 29

Законы логики Закон Для или Для и переместительный распределительный Сочетательный Идемпотенции Поглощения Операция с инверсией Операция с константами

Слайд 30

Законы для отрицания Закон Для или Для и Правило де Моргана Двойное отрицание

Слайд 31

Закон исключения (склеивания)

Слайд 32

Иногда при решении задач полезны формулы де Моргана: ¬ (A  B) = ¬ A  ¬ B ¬ (A  B) = ¬ A  ¬ B Огастес (Август) де Морган – шотландский математик и логик.

Слайд 33

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

Слайд 34

1 способ

Слайд 35

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

Слайд 36

A B C 1 2 3 4 5 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Слайд 37

A B C 1 2 3 4 5 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1

Слайд 38

A B C 1 2 3 4 5 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0

Слайд 39

A B C 1 2 3 4 5 0 0 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 1 1 1 0 1

Слайд 40

A B C 1 2 3 4 5 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 0 1 1

Слайд 41

A B C 1 2 3 4 5 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 1 1 1

Слайд 42

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

Слайд 43

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

Слайд 44

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

Слайд 45

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

Слайд 46

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

Слайд 47

D – первый или B – второй : D 1  B 2 =1 C – первый или A – четвертый : C 1  A 4 =1 D – второй или B – третий : D 2  B 3 =1 ( D 1  B 2 )( C 1  A 4 )( D 2  B 3 )=1 ( D 1 C 1  B 2 C 1  D 1 A 4  B 2 A 4 )( D 2  B 3 )=1 B 2 C 1 D 2  D 1 A 4 D 2  B 2 A 4 D 2  B 2 C 1 B 3  D 1 A 4 B 3  B 2 A 4 B 3 =1 D 1 A 4 B 3 =1 Следовательно, D – первый, С – второй, B – третий, A – четвертый.

Слайд 48

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

Слайд 49

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

Слайд 50

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

Слайд 51

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

Слайд 52

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

Слайд 53

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

Слайд 54

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

Слайд 55

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

Слайд 56

Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию. A B C F(A, B, C) 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1

Слайд 57

A B C F 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 1 1 0 1

Слайд 58

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

Слайд 59

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

Слайд 60

x 1 x 2 x 3 F(x 1 , x 2 , x 3 ) 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

Слайд 61

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

Слайд 63

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

Слайд 64

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

Слайд 65

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

Слайд 66

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

Слайд 67

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

Слайд 68

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