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

Обновлено: 30.06.2024

Презентация на тему: " Алгебра высказываний Решение Решение логических логических задач Автор: Сергеев Евгений Викторович МОУ СОШ 4 г. Миньяра Челябинской области sergeev73@mail.ru." — Транскрипт:

1 Алгебра высказываний Решение Решение логических логических задач Автор: Сергеев Евгений Викторович МОУ СОШ 4 г. Миньяра Челябинской области

5 Задача 4: Составьте таблицу истинности для функции А ¬В A0011A0011 B0101B0101 ¬B¬B A ¬ B

6 Задача 5: Какие из следующих импликаций истинны 1.если 2 2 = 4, то 2 3 3.если 2 2 = 5, то 2 3 истиналожьистинаистина Таблицы истинности

7 Задача 6: Какие из следующих высказываний противоречивы 1.a = 1, a b = 0 2.a = 1, a b = 0 3.a = 1, a b = 1 4.a = 1, a b = 1 5.a = 0, a b = 1 6.a = 0, a b = 1 7.a = 0, a b = 0 8.a = 0, a b = 0 истиналожьистинаистиналожьистинаистинаистина Таблицы истинности

9 истинаистинаистиналожьистинаистинаистинаистинаистинаистиналожьложьистинаистина Задача 8: Какие из следующих высказываний истинны 1. p p 2. p ¬p 3. ¬(p ¬p) 4. p ¬p 5. ¬p p 6. p p 7. (p p) p 8. ¬(p (p ¬p)) 9. (p p) ¬p 10. p p (¬p p p) 11. p (p ¬p) 12. ¬(¬p p) 13. ¬(p ¬p) 14. (p p) (p p)

10 Задача 9: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний 1.x (y z) 2.(x y) z 3.x (y z) 4.x y z 5.(x y) (z ¬y) 6.((x y) z) ((x z) (y z))

11 Задача 9.1: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний x (y z) x (1 1) x (ложь) x (y z) Таблицы истинности

12 Задача 9.2: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний (x y) z (0 1) z 0 z (ложь) (x y) z Таблицы истинности

13 Задача 9.3: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний x (y z) x (1 1) x (истина) x (y z) Таблицы истинности

14 Задача 9.4: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний x y z 0 1 z 0 z0 z0 z0 z (истина) x y z Таблицы истинности

15 Задача 9.5: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний (x y) (z ¬y) (x y) (z ¬1) (x y) (z 0) (0 1) (1 0) (ложь) (x y) (z ¬y) Таблицы истинности

16 Задача 9.6: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний ((x y) z) ((x z) (y z)) ((0 1) z) ((0 1) (1 1)) (( 1 ) z) (( 0 ) ( 1 )) (1 1) (0 1) (истина) ((x y) z) ((x z) (y z)) Таблицы истинности

17 Задача 10: Упростите выражение: (А В) (А ¬В) (А В) (А ¬В) А (В ¬В) А ( 1 ) А (А В) (А ¬В) Таблицы истинности

18 Задача 11: Упростите выражение: (А ¬А) В (А ¬А) В ( 1 ) В В (А ¬А) В Таблицы истинности

19 Задача 12: Упростите выражение: А (А В) (В ¬В) А (А В) (В ¬В) А (А В) ( 1 ) А (А В) 1 А 1 А А (А В) (В ¬В) Таблицы истинности

20 Задача 13: Доказать справедливость закона поглощения для дизъюнкции: А (А В) А по таблицам истинности Таблицы истинности A0011A0011 B0101B0101 A B A (А B)

21 Задача 14: Доказать справедливость закона поглощения для конъюнкции: А (А В) А по таблицам истинности Таблицы истинности A0011A0011 B0101B0101 A B A (А B)

22 Задача 15: Доказать справедливость первого закона де Моргана: ¬(А В) ¬А ¬В по таблицам истинности Таблицы истинности A0011A0011 B0101B0101 ¬A¬A ¬B¬B A B ¬(A B) ¬A ¬B

23 Задача 16: Доказать справедливость второго закона де Моргана: ¬(А В) ¬А ¬В по таблицам истинности Таблицы истинности A0011A0011 B0101B0101 ¬A¬A ¬B¬B A B ¬(A B) ¬A ¬B

24 Задача 17: Составить расписание занятий так, чтобы математика была первым или вторым уроком, информатика первым или третьим уроком, а физика – вторым или третьим. В расписании всего три урока. Сколько вариантов расписания с такими условиями можно составить?

26 Задача 17. Решение. Раскрытие скобок (М1 М2) (И1 И3) (Ф2 Ф3) (М1 И1 М1 И3 М2 И1 М2 И3) (Ф2 Ф3) М1·И1·Ф2 М1·И3·Ф2 М2·И1·Ф2 М2·И3·Ф2 М1·И1·Ф3 М1·И3·Ф3 М2·И1·Ф3 М2·И3·Ф3 Выбираем только непротиворечивые комбинации: Ответ: 1 вариант – Математика, Физика, Информатика 2 вариант – Информатика, Математика, Физика М1·И1·Ф2 М1·И3·Ф2 М2·И1·Ф2 М2·И3·Ф2 М1·И1·Ф3 М1·И3·Ф3 М2·И1·Ф3 М2·И3·Ф3

30 Задача 19. Следователь допрашивает Клода, Жака и Дика. Клод утверждает, что Жак лжет, Жак обвинял во лжи Дика, а Дик призывает не слушать ни того, ни другого. Кто из допрашиваемых говорил правду? Решение: Пусть показания свидетелей будут назваться буквами К, Ж и Д. Тогда известно, что: 1. Если Клод сказал правду (К), то Жак лжет (¬Ж), иначе (если Клод солгал, ¬К), то Жак сказал правду (Ж) 2. Если Жак сказал правду (Ж), тогда Дик не прав, (¬Д), иначе лжет Жак (¬Ж), а Дик – прав (Д) 3. Если лжет Дик (Д), то Клод и Жак правы (Ж и К), иначе последние лгут (¬(Ж и К)), а Дик – прав (Д)

31 Задача 19. Решение Выразим эти высказывания на формальном языке логики: 1. К ¬Ж ¬К Ж 2. Ж ¬Д ¬Ж Д 3. Д ¬К ¬Ж ¬Д (К Ж) Задача будет решена, если все три высказывания будут истинны, т.е. истинна их конъюнкция: (К·¬Ж ¬К·Ж) (Ж·¬Д ¬Ж·Д) (Д·¬К·¬Ж ¬Д·(К Ж)) (К·¬Ж · Ж·¬Д К·¬Ж · ¬Ж·Д ¬К·Ж · Ж·¬Д ¬К·Ж · ¬Ж·Д) (К·¬Ж · Ж·¬Д К·¬Ж · ¬Ж·Д ¬К·Ж · Ж·¬Д ¬К·Ж · ¬Ж·Д) (Д·¬К·¬Ж ¬Д·К ¬Д·Ж) (Д·¬К·¬Ж ¬Д·К ¬Д·Ж) (К·¬Ж · ¬Ж·Д ¬К·Ж · Ж·¬Д) (Д·¬К·¬Ж ¬Д·К ¬Д·Ж) (К·¬Ж · ¬Ж·Д·Д·¬К·¬Ж К·¬Ж · ¬Ж·Д·¬Д·Ж К·¬Ж · ¬Ж·Д·¬Д·Ж ¬К·Ж · Ж·¬Д·Д·¬К·¬Ж ¬К·Ж · Ж·¬Д·¬Д·Ж ¬К·Ж · Ж·¬Д·¬Д·Ж ¬К·Ж · Ж·¬Д·¬Д·Ж ¬К·Ж · Ж·¬Д·¬Д·Ж ¬К ¬Д Ж Итак, только Жак говорил правду (К·¬Ж ¬К·Ж) (Ж·¬Д ¬Ж·Д) (Д·¬К·¬Ж ¬Д·(К Ж))

34 Таблицы истинности Конъюнкция A0011A0011 B0101B0101 A B 0 1 Дизъюнкция A0011A0011 B0101B0101 А В 0 1 Импликация A0011A0011 B0101B0101 A B Эквиваленция A0011A0011 B0101B0101 А В

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

Информатика. 10 класса. Босова Л.Л. Оглавление

§ 20. Преобразование логических выражений

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

20.1. Основные законы алгебры логики.

Приведём основные законы алгебры логики.

1. Переместительные (коммутативные) законы:

2. Сочетательные (ассоциативные) законы:

(A v В) v С = A v (В v С).

3. Распределительные (дистрибутивные) законы:

A v (В & С) = (A v В) & (A v С).

4. Законы идемпотентности (отсутствия степеней и коэффициентов):

5. Закон противоречия:

6. Закон исключённого третьего:

7. Закон двойного отрицания:

8. Законы работы с константами:

A v 1 = 1; A v O = A;

9. Законы де Моргана:

10. Законы поглощения:

Справедливость законов можно доказать построением таблиц истинности.

Пример 1. Упростим логическое выражение

Последовательно применим дистрибутивный закон и закон исключённого третьего:

Пример 2. Упростим логическое выражение

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

Пробуйте самостоятельно доказать один из этих законов с помощью кругов Эйлера.

Пример 3. На числовой прямой даны отрезки В = [2; 12] и С = [7; 18]. Каким должен быть отрезок А, чтобы предикат

становился истинным высказыванием при любых значениях х.

Преобразуем исходное выражение, избавившись от импликации:

причём это минимально возможное множество А.

Множество В — это отрезок [2; 12].

Изобразим это графически:

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

Чему равна минимальная длина отрезка А? Укажите ещё несколько вариантов множества А.

Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение

тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

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

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

Перепишем исходное выражение в наших обозначениях:

Рассмотрим предикат М(х) = (х & 28 ? 0). В числе 28 = 11100₂ 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание х & 28 ? 0 будет ложным.

Рассмотрим предикат N(x) = (х & 45 ? 0). В числе 45 = 101101₂ 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули.

Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание х & 45 ? 0 будет ложным.

Рассмотрим предикат К(х) = (х & 17 = 0). В числе 17 = 10001₂ 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна нулю, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.

По условию задачи надо, чтобы

Запишем это выражение для рассмотренных множеств истинности:

Объединением множеств М и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством К будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т. е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.

Искомое число а должно быть таким, чтобы при любом неотрицательном целом значении переменной х: х & а ? 0, и кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 101100₂. Действительно, единицы в нём стоят в тех и только в тех битах, которые нужны для выполнения условия х & а ? 0.

Итак, требуемое число 101100₂ или 44₁₀.

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

Пример 5. Выясним, сколько решений имеет следующая система из двух уравнений:

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

Начнем строить дерево решений, представив на нём значения переменных х₁ и х₂ при которых х₁ ? х₂ = 1.

Продолжим строить дерево решений. Значения переменной х₃ будем выбирать такими, чтобы при имеющихся х₂ импликация х₂ ? х₃ оставалась истинной.

То же самое проделаем для переменной х₄.

На дереве видно, что рассматриваемое нами уравнение имеет 5 решений — 5 разных наборов значений логических переменных x₁, х₂, х₃, х₄, при которых выполняется равенство:

Следовательно, как и первое уравнение, это уравнение имеет 5 решений. Представим их в табличной форме:

Решение исходной системы логических уравнений — это множество различных наборов значений логических переменных х₁, х₂, х₃, х₄, у₁, у₂, у₃, у₄ таких, что при подстановке каждого из них в систему оба уравнения превращаются в истинные равенства.

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

Всего мы можем построить 5 • 5 = 25 решений системы.

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

20.2. Логические функции

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

Совокупность значений п аргументов удобно интерпретировать как строку нулей и единиц длины n. Существует ровно 2 n различных двоичных строк длины n. Так как на каждой такой строке некая функция может принимать значение 0 или 1, общее количество различных булевых функций от n аргументов равно

Для n = 2 существует 16 различных логических функций.

Рассмотрим их подробнее.

С увеличением числа аргументов количество логических функций резко возрастает. Так, для трёх переменных существует 256 различных логических функций! Но изучать их все нет никакой необходимости. Дело в том, что путём преобразований функция любого количества переменных может быть выражена через функции только двух переменных. Более того, можно использовать не все, а лишь некоторые логические функции двух переменных. Например:

1) F₂ и F₁₁ (конъюнкция и отрицание второго аргумента);

2) F₈ и F₁₃ (дизъюнкция и отрицание первого аргумента);

3) F₉ (стрелка Пирса, отрицание дизъюнкции);

4) F₁₅ (штрих Шеффера, отрицание конъюнкции).

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

20.3. Составление логического выражения по таблице истинности и его упрощение

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

Алгоритм составления логического выражения по таблице истинности достаточно прост. Для этого надо:

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

Пример 6. Имеется следующая таблица истинности:

После выполнения двух первых шагов алгоритма получим:

После выполнения третьего шага получаем логическое выражение:

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

, а далее используем законы алгебры логики.

САМОЕ ГЛАВНОЕ

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

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

Вопросы и задания

Известно, что выражение

истинно при любом значении переменной х. Определите наименьшее возможное количество элементов множества А.

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

Проанализируем составное высказывание. Оно состоит из следующих простых высказываний: "Петя поедет в деревню", "Будет хорошая погода", "Он пойдет на рыбалку". Обозначим их через логические переменные:

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

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

Пример: Людоед голоден только тогда, когда он давно не ел.
Обозначим посылкой A - , следствием B - , тогда формула примет вид
Правильно ли записана формула? обычно встречалось условие с "если ,то" по нему и решал, изменяется ли что то при условии "только тогда, когда"?

Записать в виде формул логики предикатов высказывания о множествах
Не могу понять как решить задание На координатной плоскости даны множества А и В( А-красным.

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

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

Записать высказывание в виде формулы логики высказываний
А, когда В и С, а В при условии, что С, но из С не следует А и В.

Читайте также: