Методы решения логических уравнений презентация

Логические уравнения
презентация к уроку по информатике и икт (10 класс)

Скачать:

Предварительный просмотр:

Подписи к слайдам:

I способ II способ Все решения уравнения

I I I способ A B C D Ø A 0 0 0 0 ИСТИНА ИСТИНА 0 0 0 1 ИСТИНА ИСТИНА 0 0 1 0 ИСТИНА ИСТИНА 0 1 0 0 ИСТИНА ИСТИНА 1 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 ЛОЖЬ ИСТИНА 0 1 1 1 ИСТИНА ИСТИНА 1 1 1 0 ЛОЖЬ ИСТИНА 1 1 0 1 ЛОЖЬ ИСТИНА 1 0 1 1 ЛОЖЬ ИСТИНА 1 1 1 1 ЛОЖЬ ИСТИНА Все решения уравнения

Количество решений 4 решения 16 решений – 4 решения = 12 решений

Системы логических уравнений Импликация А В ложна только тогда, когда A=1 и B =0. Тогда первое уравнение имеет 6 решений: 00000 00001 00011 00111 01111 11111 Второе уравнение имеет 5 решений: 0000 0001 0011 0111 1111 Уравнения независимы, поэтому общее количество решений 5*6=30.

Синтез логических выражений A B X 0 0 1 0 1 1 1 0 0 1 1 1 Дизъюнкция простых конъюнкций – дизъюнктивная нормальная форма (ДНФ). I способ II способ A B  X 0 0 0 0 1 0 1 0 1 1 1 0

Множества и логические выражения Задача 1. A должны быть истинно для всех случаев, когда B =0 ( для объектов не входящих во множество B ). A может быть истинно для некоторых значений множества B . Минимальное множество удовлетворяющее условию. Задача 2.

Множества и логические выражения Задача 3. Выбираем наибольший отрезок – отрезок q . Задача 4.

По теме: методические разработки, презентации и конспекты

Кодирование текстовой информации.Решение логических уравнений.

Материал разработан для подготовки учащихся к ЕГЭ. Предложены задачи и их решение.

статья «Решение системы логических уравнений»

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

Подготовка к ЕГЭ. Разбор решений систем логических уравнений.

В презентации рассмотрены примеры решения заданий В15 по теме «Решение логических уравнений».

контрольная работа»Логические уравнения» 11 класс (профильный уровень)

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

Методы решения систем логических уравнений

Методы решения систем логических уравнений при подготовке к ЕГЭ (задание В15).

Решение логических уравнений и систем логических уравнений

Логические уравнения и системы логических уравнений в ЕГЭ

Данной материал содержит презентацию, в которой представлены методы решения логических уравнений и систем логических уравнений в задании В15 (№ 23, 2015) ЕГЭ по информатике. Известно, что это задание .

Презентация «Основные подходы к решению логических уравнений»

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

«Актуальность создания школьных служб примирения/медиации в образовательных организациях»

Свидетельство и скидка на обучение каждому участнику

Описание презентации по отдельным слайдам:

Основные подходы к решению логических уравнений. Способы решения систем логических уравнений Н.М.Борисова, учитель информатики ГБОУ СОШ №249 имени М.В.Маневича Кировского района Санкт-Петербурга

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

Необходимые знания Обозначения, таблицы истинности, свойства логических операций (конъюнкция, дизъюнкция, инверсия, эквиваленция, исключающее «или») Приоритет логических операций Законы алгебры логики Формулы представления импликации, эквиваленции, исключающего «или»:

Таблицы истинности логических операций A B A&B AvB AB A B AB 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0

Некоторые приемы: Замена переменных для независимых повторяющихся выражений Наблюдения закономерностей роста количества решений при добавлении переменных или уравнений Правила комбинаторики (правила суммы и произведения) Нет единого алгоритма решения!

Пример:Сколько различных решений имеет система уравнений Ответ:0 1 0 = 0 у6=0 1 0 = 0 у6=1 Решение: Решаем с конца. Из последнего уравнения y6 y1= 0 следует, что y6=1. Из предпоследнего уравнения х1 y6 = 0 следует, что у6=0. Получаем противоречие, т.к. переменная у6 не может одновременно быть и 0, и 1. Вывод- система решений не имеет.

Пример1:Сколько различных решений имеет система уравнений ¬(x1 ≡ x2) /\ ¬(x2 ≡ x3) =1 ¬(x2 ≡ x3) /\ ¬(x3 ≡ x4) =1 . ¬(x8 ≡ x9) /\ ¬(x9 ≡ x10) =1 где x1, x2, . x10 – логические переменные?  ¬(x1 ≡ x2) =1 ¬(x2 ≡ x3) =1 … ¬(x9 ≡ x10) =1  x1 ≡ x2=0  x2 ≡ x3=0 … x9 ≡ x10 =0 х1 х2 х3… х9 х10 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 2 x1≠x2 x2≠x3 … x9≠x10

Пример1:Сколько различных решений имеет система уравнений (x1  x2)  (x2  x3) =1 (x2  x3)  (x3  x4) =1 . (x8  x9)  (x9  x10) =1 где x1, x2, . x10 – логические переменные? х1 х2 х3… х9 х10 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 ответ: 2 x1≠x2 x2≠x3 … x9≠x10  x1=x2

Пример 2: Определить, сколько различных решений имеет система уравнений:

2 способ(преобразовать и решать с конца) Из последнего уравнения имеем: х1 и х5 одного значения x1=x5=0 или x1=x5=1 0***0 1***1 (1) (2) (3) (4) Из уравнения (3) имеем: х4 одного значения с х1 и х5 0**00 1**11 Из уравнения (2) имеем: х3 одного значения с х1 и х4 0*000 1*111 Из уравнения (1) имеем: х2 одного значения с х1 и х3 00000 11111 Ответ: 2

Задача Сколько существует различных наборов значений логических переменных x1, х2, х3, х4, х5, y1, у2, у3, у4, у5, которые удовлетворяют всем перечисленным ниже условиям? (x1→ x2)  (x2→x3)  (x3→x4)  (x4→ x5) = 1; (y1→ y2)  (y2→y3)  (y3→y4)  (y4→ y5) = 1; y5 → x5 = 1. В ответе не нужно перечислять все различные наборы значений переменных x1, х2, х3, х4, х5, y1, у2, у3, у4, у5, при которых выполнена данная система равенств. В качестве ответа нужно указать количество таких наборов.

x1x2x3 x4 x5 011 1 1 011 1 01 1 0 1 0 111 1 1 6 (x1→ x2)  (x2→x3)  (x3→x4) (x4→ x5) = 1;

Для n переменных (x1 x2x3x4… xn) уравнение имеет (n+1) решений (x1→ x2)  (x2→x3)  (x3→x4) …(Xn-1→ Xn) = 1; x1 x2 x3 x4 x5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1

y1y2y3y4 y5 011 1 1 011 1 01 1 0 1 0 111 1 1 6 6*6=36 решений (x1→ x2)  (x2→x3)  (x3→x4)  (x4→ x5) = 1; (y1→ y2)  (y2→y3)  (y3→y4)  (y4→ y5) = 1;

y1 y2 y3 y4 y5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 x1 x2 x3 x4 x5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 6 решений 5 решений 5 решений 5 решений 5 решений 5 решений 6+5+5+5+5+5=31 (x1→ x2)  (x2→x3)  (x3→x4)  (x4→ x5) = 1; (y1→ y2)  (y2→y3)  (y3→y4)  (y4→ y5) = 1; y5 → x5 = 1 — ключ

матрица решений Ответ: 31 решение. (x1→ x2)  (x2→x3)  (x3→x4)  (x4→ x5) = 1; (y1→ y2)  (y2→y3)  (y3→y4)  (y4→ y5) = 1; y5 → x5 = 1 — ключ Кол-во вариантов (пар) (00000) (00001) (00011) (00111) (01111) (11111) (00000) + + + + + + 6 (00001) – + + + + + 5 (00011) – + + + + + 5 (00111) – + + + + + 5 (01111) – + + + + + 5 (11111) – + + + + + 5 Всего возможных вариантов (пар) наборов значений и: 31

x1 x2 x3 x4 x5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 y1 y2 y3 y4 y5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 6 решений 6 решений 6 решений 6 решений 6 решений 1 решение 6+6+6+6+6+1=31 (x1→ x2)  (x2→x3)  (x3→x4)  (x4→ x5) = 1; (y1→ y2)  (y2→y3)  (y3→y4)  (y4→ y5) = 1; x1→ y1= 1 — другой ключ

Строим матрицу решений Ответ: 31 решение. x1→ y1= 1 — ключ Кол-во вариантов (пар) (00000) (00001) (00011) (00111) (01111) (11111) (00000) + + + + + + 6 (00001) + + + + + + 6 (00011) + + + + + + 6 (00111) + + + + + + 6 (01111) + + + + + + 6 (11111) – – – – – + 1 Всего возможных вариантов (пар) наборов значений: 31

Метод отображений (Мирончик Ел. А., Мирончик Ек. А.) МБ НОУ «Лицей №111», г. Новокузнецк

Решение логических уравнений Задача1. Найти число решений уравнения х1 х2  х3  х4  х5=1 х1 х2  х3  х4  х5  х6  х7 =1 х1 х2  х3  х4  х5 …  хn =1

Задача1. Найти число решений уравнения х1 х2  х3  х4  х5=1 (((х1 х2 ) х3)  х4)  х5=1 1 2 3 4

Таблица истинности для импликации Отражение множеств х1 Х1 х2 0 1 0 1 x1 x2 x1x2 0 0 1 1 1 1 0 0 1 1

Таблица истинности для импликации Отражение множеств х1 Х1 х2 0 1 0 1 x1 x2 x1x2 0 0 1 1 1 1 0 0 1 1

Таблица для определения количества 0 и 1 х1 х2  х3  х4  х5=1 х1 Х1 х2 0 1 0 1 Количество «0» и «1»i-го после действия х1 1 х1х2 2 …х3 3 …х4 4 …х5 «0» «1»

Таблица для определения количества 0 и 1 х1 х2  х3  х4  х5=1 Ответ:21 х1 Х1 х2 0 1 0 1 Количество «0» и «1»i-го после действия х1 1 х1х2 2 …х3 3 …х4 4 …х5 «0» 1 1 3 5 11 «1» 1 3 5 11 21

х1 х2  х3  х4 … х10=1 х1 Х1 х2 0 1 0 1 Количество после действия х1 1 х1х2 2 …х3 3 …х4 4 …х5 5 …х6 6 …х7 «0» 1 1 3 5 11 21 43 «1» 1 3 5 11 21 43 85

х1 х2  х3  х4 … х10=1 х1 Х1 х2 0 1 0 1 Количество после действия х1 1 х1х2 2 …х3 3 …х4 4 …х5 5 …х6 6 …х7 «0» 1 1 3 5 11 21 43 «1» 1 3 5 11 21 43 85 2 4 8 16 32 64 128

-Выражения в скобках не зависят друг от друга; -Таблица для второй скобки повторяет часть таблицы для первой скобки.

Таблица1 для первой скобки =1 Таблица2

Таблица1 =1 Таблица2 Ответ:95 Всего 27 = 128 строк в таблице, Строк=0 всего33 (1  0 =0), Значит остальные 128-33=95 равны 1.

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

Метод отображения для систем уравнений

Метод отображения для систем уравнений 0 1 0 1 1 0 1 1. x1 x2 x3 0 0 1 1 0 1

00 01 10 11 00 01 10 11 x1x2 x2x3 x1 x2 x3 0 0 0 1 1 0 1 1 0 1 1 0 1

Пусть F(..) это функция, вычисляющая количество пар на следующем шаге. 00 01 10 11 00 01 10 11 x1x2 x2x3 F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11)

232 F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11) + Ответ:232 2 2 2 1 3 4 4 1 5 7 7 1 8 12 12 1 13 20 20 1 21 33 33 1 34 54 54 1 55 88 88 1 Пара Количество пар x1,x2 x2,x3 x3,x4 x4,x5 x5,x6 x6,x7 x7,x8 x8,x9 x9,x10 00 1 01 1 10 1 11 1

Система с ключевым уравнением: 2.

143 F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11) Схема решения та же 1 1 1 1 2 2 2 1 3 4 4 1 5 7 7 1 8 12 12 1 13 20 20 1 21 33 33 1 34 54 54 1 Пара Количество пар x1,x2 x2,x3 x3,x4 x4,x5 x5,x6 x6,x7 x7,x8 x8,x9 x9,x10 00 1 01 1 10 0 11 0

Система с ключевым уравнением: 2. х11 по ключу F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11) Схема решения та же Ответ:143

Система с ключевым уравнением: 3.

124 F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11) Схема решения та же 2 2 2 1 3 4 4 1 5 7 7 1 8 0 12 0 12 8 8 0 8 20 20 0 20 28 28 0 28 48 48 0 Пара Количество пар x1,x2 x2,x3 x3,x4 x4,x5 x5,x6 x6,x7 x7,x8 x8,x9 x9,x10 00 1 01 1 10 1 11 1

Система с ключевым уравнением: 3. По ключу значения x5 и x6 должны быть разными. Это значит, что в таблице в столбце x6 необходимо обнулить значения, соответствующие парам 00 и 11. F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11) Схема решения та же Ответ:124 -ключ

4 56 F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11) 2 2 2 1 3 4 4 1 5 7 7 1 8 12 12 1 13 20 20 1 21 33 33 1 0 0 54 1 55 0 0 1 Пара Количество пар x1,x2 x2,x3 x3,x4 x4,x5 x5,x6 x6,x7 x7,x8 x8,x9 x9,x10 00 1 01 1 10 1 11 1

5. 52 F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11) 1 1 1 1 2 2 2 1 0 0 4 1 5 0 0 1 1 5 5 1 6 6 6 1 7 12 12 1 13 19 19 1 Пара Количество пар x1,x2 x2,x3 x3,x4 x4,x5 x5,x6 x6,x7 x7,x8 x8,x9 x9,x10 00 1 01 1 10 0 11 0

65 52 решения 65 решений Ответ: 117 решений F (00) = F (00) F (01) = F (00) + F (10) F (10) = F (01) + F (11) F (11) = F (01) + F (11) 1 1 1 0 1 2 2 0 2 3 0 0 0 5 5 0 5 5 5 0 5 10 10 0 10 15 15 0 15 25 25 0 Пара Количество пар x1,x2 x2,x3 x3,x4 x4,x5 x5,x6 x6,x7 x7,x8 x8,x9 x9,x10 00 0 01 0 10 1 11 1

1. 00 00 01 01 10 10 11 11 … x1 x2 x3 0 0 0 1 1 0 1 1 0 0 1 1 0 1

55+34+34+55 = 178 решений x1x2 x2x3 00 00 01 01 10 10 11 11 … x1x2 x2x3 x3x4 x4x5 x5x6 x6x7 x7x8 x8x9 x9x10 00 1 2 3 5 8 13 21 34 55 01 1 1 2 3 5 8 13 21 34 10 1 1 2 3 5 8 13 21 34 11 1 2 3 5 8 13 21 34 55

2. Сколько различных решений имеет система уравнений X1  X2  X3 = 1 X2  X3  X4 = 1 . X8  X9  X10 = 1 x1x2 x2x3 00 00 01 01 10 10 11 11 x1 x2 x3 0 0 0 1 1 0 1 1 0 0 1 1 0 1

13 + 13 + 19 + 28 = 73 решения x1x2 x2x3 00 00 01 01 10 10 11 11 x1x2 x2x3 x3x4 x4x5 x5x6 x6x7 x7x8 x8x9 x9x10 00 0 1 1 2 3 4 6 9 13 01 1 1 1 2 3 4 6 9 13 10 1 1 2 3 4 6 9 13 19 11 1 2 3 4 6 9 13 19 28

Источники информации http://kpolyakov.narod.ru/school/ege.htm, [Электронный ресурс] К.Ю. Поляков. Логические уравнения // Информатика, № 14, 2011, с. 30-35. Метод отображения, Мирончик Е.А., МБ НОУ «Лицей №111», г. Новокузнецк М.А. Ройтберг, д. ф.-м. н., г. Пущино, http://ege-go.ru декабрь 2014 / ИНФОРМАТИКА Системы логических уравнений: решение с помощью битовых цепочек

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

• Сейчас обучается 952 человека из 80 регионов

Курс повышения квалификации

Педагогическая деятельность в контексте профессионального стандарта педагога и ФГОС

• Курс добавлен 23.11.2021
• Сейчас обучается 49 человек из 30 регионов

Курс повышения квалификации

Инструменты онлайн-обучения на примере программ Zoom, Skype, Microsoft Teams, Bandicam

• Курс добавлен 31.01.2022
• Сейчас обучается 33 человека из 19 регионов

Ищем педагогов в команду «Инфоурок»

Дистанционные курсы для педагогов

Самые массовые международные дистанционные

Школьные Инфоконкурсы 2022

33 конкурса для учеников 1–11 классов и дошкольников от проекта «Инфоурок»

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

5 565 044 материала в базе

Материал подходит для УМК

«Информатика (базовый уровень)», Семакин И.Г., Хеннер Е.К., Шеина Т.Ю.

Другие материалы

• 05.06.2018
• 1297
• 7

• 04.06.2018
• 1213
• 1

• 04.06.2018
• 4298
• 116

• 03.06.2018
• 1751
• 3

• 01.06.2018
• 308
• 0

• 01.06.2018
• 1062
• 6

• 31.05.2018
• 328
• 0

• 31.05.2018
• 1534
• 155

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Добавить в избранное

• 05.06.2018 1415
• PPTX 1.2 мбайт
• 26 скачиваний
• Рейтинг: 3 из 5
• Оцените материал:

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

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Автор материала

• На сайте: 6 лет и 4 месяца
• Подписчики: 1
• Всего просмотров: 61023
• Всего материалов: 38

Московский институт профессиональной
переподготовки и повышения
квалификации педагогов

Дистанционные курсы
для педагогов

663 курса от 690 рублей

Выбрать курс со скидкой

Выдаём документы
установленного образца!

Учителя о ЕГЭ: секреты успешной подготовки

Время чтения: 11 минут

Объявлен конкурс дизайн-проектов для школьных пространств

Время чтения: 2 минуты

В Рособрнадзоре рассказали, как будет меняться ЕГЭ

Время чтения: 2 минуты

Онлайн-конференция о создании школьных служб примирения

Время чтения: 3 минуты

ЕГЭ в 2022 году будут сдавать почти 737 тыс. человек

Время чтения: 2 минуты

Тринадцатилетняя школьница из Индии разработала приложение против буллинга

Время чтения: 1 минута

Профессия педагога на третьем месте по популярности среди абитуриентов

Время чтения: 1 минута

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

презентация Решение логических уравнений

Данная презентация предназначена для подготовки к ГИА-11. Решение системы логических уравнений является самым сложным заданием в первой части экзаменационных материалов по информатике. В презентации даны решения некоторых систем логических уравнений.

Выходные данные (библиографическая ссылка):

Смирнов А. Н. Решение логических уравнений // Международный каталог для учителей, учеников и преподавателей «Презентации» // URL: https://edupres.ru/prezentatsii-po-informatike/11-klass/file/24964-reshenie-logicheskikh-uravnenij (дата обращения: 15.02.2022)

Авторскими правами на размещенную информацию обладают её авторы (создатели презентаций), которые также несут ответственность за её достоверность. Редакция сайта не отвечает за качество авторских продуктов. Все материалы доступны по лицензии Creative Commons.

Копирование материалов каталога с целью размещения на своём сайте разрешается только при наличии ссылки на каталог Презентации.

© 2015—2022 Все права защищены. Презентации
Разработка сайта — Griban