Логические уравнения. Решение логических уравнений по математике Решение системы логических уравнений по информатике онлайн

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

Скачать:

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

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com

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

Решение задания В15 (системы логических уравнений) Вишневская М.П., МАОУ «Гимназия №3» 18 ноября 2013 г., г. Саратов

Задание В15 - одно из самых сложных в ЕГЭ по информатике!!! Проверяются умения: преобразовывать выражения, содержащие логические переменные; описывать на естественном языке множество значений логических переменных, при которых заданный набор логических переменных истинен; подсчитывать число двоичных наборов, удовлетворяющих заданным условиям. Самое сложное, т.к. нет формальных правил, как это сделать, требуется догадка.

Без чего не обойтись!

Без чего не обойтись!

Условные обозначения конъюнкция: A /\ B , A  B , AB , А &B, A and B дизъюнкция: A \ / B , A + B , A | B , А or B отрицание:  A , А, not A эквиваленция: A  В, A  B, A  B исключающее «или»: A  B , A xor B

Метод замены переменных Сколько существует различных наборов значений логических переменных х1, х2, …, х9, х10, которые удовлетворяют всем перечисленным ниже условиям: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 В ответе не нужно перечислять все различные наборы х1, х2, …, х9, х10, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов (демо-версия 2012 г.)

Решение Шаг 1. Упрощаем, выполнив замену переменных t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 После упрощения: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ (¬t4 \/ ¬ t5) =1 Рассмотрим одно из уравнений: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Очевидно, оно =1 только если одна из переменных равна 0, а другая – 1. Воспользуемся формулой для выражения операции XOR через конъюнкцию и дизъюнкцию: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Шаг2. Анализ системы ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т.к. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), то каждому значению tk соответствует две пары значений x2k-1 и x2k , например: tk =0 соответствуют две пары - (0,1) и (1,0) , а tk =1 – пары (0,0) и (1,1).

Шаг3. Подсчет числа решений. Каждое t имеет 2 решения, количество t – 5. Т.о. для переменных t существует 2 5 = 32 решения. Но каждому t соответствует пара решений х, т.е. исходная система имеет 2*32 = 64 решения. Ответ: 64

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

Решение. Шаг1. Последовательное решение уравнений х1 1 0 х2 1 0 1 х3 1 0 1 1 х4 1 0 1 1 1 х5 1 0 1 1 1 1 Первое уравнение – конъюнкция нескольких операций импликации, равна 1, т.е. каждая из импликаций истинна. Импликация ложна только в одном случае, когда 1  0, во всех других случаях (0  0, 0  1, 1  1) операция возвращает 1. Запишем это в виде таблицы:

Шаг1. Последовательное решение уравнений Т.о. получено 6 наборов решений для х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Рассуждая аналогично, приходим к выводу, что для y1, y2, y3, y4, y5 существует такой же набор решений. Т.к. уравнения эти независимы, т.е. в них нет общих переменных, то решением этой системы уравнений (без учета третьего уравнения) будет 6*6= 36 пар «иксов» и «игреков». Рассмотрим третье уравнение: y5→ x5 =1 Решением являются пары: 0 0 0 1 1 1 Не является решением пара: 1 0

Сопоставим полученные решения Там, где y5 =1, не подходят x5=0. таких пар 5. Количество решений системы: 36-5= 31 . Ответ: 31 Понадобилась комбинаторика!!!

Метод динамического программирования Сколько различных решений имеет логическое уравнение x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, где x 1, x 2, …, x 6 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количеств о таких наборов.

Решение Шаг1. Анализ условия Слева в уравнении последовательно записаны операции импликации, приоритет одинаков. Перепишем: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Каждая следующая переменная зависит не от предыдущей, а от результата предыдущей импликации!

Шаг2. Выявление закономерности Рассмотрим первую импликацию, X 1 → X 2. Таблица истинности: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Из одного 0 получили 2 единицы, а из 1 получили один 0 и одну 1. Всего один 0 и три 1, это результат первой операции.

Шаг2. Выявление закономерности Подключив к результату первой операции x 3 , получим: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Из двух 0 – две 1, из каждой 1 (их 3) по одному 0 и 1 (3+3)

Шаг 3. Вывод формулы Т.о. можно составить формулы для вычисления количества нулей N i и количества единиц E i для уравнения с i переменными: ,

Шаг 4. Заполнение таблицы Заполним слева направо таблицу для i = 6, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец по предыдущему: : число переменных 1 2 3 4 5 6 Число нулей N i 1 1 3 5 11 21 Число единиц E i 1 2*1+1= 3 2*1+3= 5 11 21 43 Ответ: 43

Метод с использованием упрощений логических выражений Сколько различных решений имеет уравнение ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 где J , K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J , K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Решение Заметим, что J → K = ¬ J  K Введем замену переменных: J → K=А, M  N  L =В Перепишем уравнение с учетом замены: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Очевидно, что A  B при одинаковых значениях А и В 6. Рассмотрим последнюю импликацию M → J =1 Это возможно, если: M=J=0 M=0, J=1 M=J=1

Решение Т.к. A  B , то При M=J=0 получаем 1 + К=0. Нет решений. При M=0, J=1 получаем 0 + К=0, К=0, а N и L - любые, 4 решения: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Решение 10. При M=J=1 получаем 0+К=1 *N * L , или K=N*L, 4 решения: 11. Итого имеет 4+4=8 решений Ответ: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Источники информации: О.Б. Богомолова, Д.Ю. Усенков. В15: новые задачи и новое решение // Информатика, № 6, 2012, с. 35 – 39. К.Ю. Поляков. Логические уравнения // Информатика, № 14, 2011, с. 30-35. http://ege-go.ru/zadania/grb/b15/ , [ Электронный ресурс ] . http://kpolyakov.narod.ru/school/ege.htm , [ Электронный ресурс ] .

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логические переменные?

Решение.

Выражение (N ∨ ¬N) истинно при любом N, поэтому

J ∧ ¬K ∧ L ∧ ¬M = 0.

Применим отрицание к обеим частям логического уравнения и используем закон де Моргана ¬ (А ∧ В) = ¬ А ∨ ¬ В. Получим ¬J ∨ K ∨ ¬L ∨ M = 1.

Логическая сумма равна 1, если хотя бы одно из составляющих ее высказываний равно 1. Поэтому полученному уравнению удовлетворяют любые комбинации логических переменных кроме случая, когда все входящие в уравнение величины равны 0. Каждая из 4 переменных может быть равна либо 1, либо 0, поэтому всевозможных комбинаций 2·2·2·2 = 16. Следовательно, уравнение имеет 16 −1 = 15 решений.

Осталось заметить, что найденные 15 решений соответствуют любому из двух возможных значений значений логической переменной N, поэтому исходное уравнение имеет 30 решений.

Ответ: 30

Сколько различных решений имеет уравнение

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

где J, K, L, M, N – логические переменные?

В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение.

Используем формулы A → B = ¬A ∨ B и ¬(А ∨ В) = ¬А ∧ ¬В

Рассмотрим первую подформулу:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Рассмотрим вторую подформулу

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Рассмотрим третью подформулу

1) M → J = 1 следовательно,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Объединим:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 следовательно, 4 решения.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Объединим:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L следовательно, 4 решения.

в) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Ответ: 4 + 4 = 8.

Ответ: 8

Сколько различных решений имеет уравнение

((K ∨ L) → (L ∧ M ∧ N)) = 0

где K, L, M, N – логические переменные? В Ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве Ответа Вам нужно указать количество таких наборов.

Решение.

перепишем уравнение, используя более простые обозначения операций:

((K + L) → (L · M · N)) = 0

1) из таблицы истинности операции «импликация» (см. первую задачу) следует, что это равенство верно тогда и только тогда, когда одновременно

K + L = 1 и L · M · N = 0

2) из первого уравнения следует, что хотя бы одна из переменных, K или L, равна 1 (или обе вместе); поэтому рассмотрим три случая

3) если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения

4) если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

5) если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

6) всего получаем 4 + 3 + 3 = 10 решений.

Ответ: 10

Сколько различных решений имеет уравнение

(K ∧ L) ∨ (M ∧ N) = 1

Решение.

Выражение истинно в трех случаях, когда (K ∧ L) и (M ∧ N) равны соответственно 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N равны 1, а K и L любые, кроме как одновременно 1. Следовательно, 3 решения.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 решение.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 решения.

Ответ: 7.

Ответ: 7

Сколько различных решений имеет уравнение

(X ∧ Y ∨ Z) → (Z ∨ P) = 0

где X, Y, Z, P – логические переменные? В ответе не нужно перечислять все различные наборы значений, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение.

(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Логическое ИЛИ ложно только в одном случае: когда оба выражения ложны.

Следовательно,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Следовательно, существует только одно решение уравнения.

Ответ: 1

Сколько различных решений имеет уравнение

(K ∨ L) ∧ (M ∨ N) = 1

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение.

Логическое И истинно только в одном случае: когда все выражения истинны.

K ∨ L = 1, M ∨ N = 1.

Каждое из уравнений дает по 3 решения.

Рассмотрим уравнение А ∧ В = 1 если и А и В принимают истинные значения в трех случаях каждое, то в целом уравнение имеет 9 решений.

Следовательно ответ 9.

Ответ: 9

Сколько различных решений имеет уравнение

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

где A, B, C, D – логические переменные?

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

Решение.

Логическое "ИЛИ" истинно, когда истинно хотя бы одно из утверждений.

(D ∧ ¬D)= 0 при любых D.

Следовательно,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, что дает нам 3 варианта решений при каждом D.

(D ∧ ¬ D)= 0 при любых D, что дает нам два варианта решений (при D = 1, D = 0).

Следовательно: всего решений 2*3 = 6.

Итого 6 решений.

Ответ: 6

Сколько различных решений имеет уравнение

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение.

Применим отрицание к обеим частям уравнения:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Логическое ИЛИ истинно в трех случаях.

Вариант 1.

K ∧ L ∧ M = 1, тогда K, L, M = 1, а ¬L ∧ M ∧ N = 0. N любое, то есть 2 решения.

Вариант 2.

¬L ∧ M ∧ N = 1, тогда N, M = 1; L = 0, K любое, то есть 2 решения.

Следовательно, ответ 4.

Ответ: 4

A, B и С — целые числа, для которых истинно высказывание

¬ (А = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(С > B)).

Чему равно В, если A = 45 и C = 43?

Решение.

Обратим внимание, что это сложное высказывание состоит из трех простых

1) ¬(А = B); (A > B)→(B > C); (B > A)→(С > B);

2) эти простые высказывания связаны операцией ∧ (И, конъюнкция), то есть, они должны выполняться одновременно;

3) из ¬(А = B)=1 сразу следует, что А B;

4) предположим, что A > B, тогда из второго условия получаем 1→(B > C)=1; это выражение может быть истинно тогда и только тогда, когда B > C = 1;

5) поэтому имеем A > B > C, этому условию соответствует только число 44;

6) на всякий случай проверим и вариант A 0 →(B > C)=1;

это выражение истинно при любом B; теперь смотрим третье условие получаем

это выражение может быть истинно тогда и только тогда, когда C > B, и тут мы получили противоречие, потому что нет такого числа B, для которого C > B > A.

Ответ: 44.

Ответ: 44

Составьте таблицу истинности для логической функции

X = (А ↔ B) ∨ ¬(A → (B ∨ C))

в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В — числа 77, столбец значений аргумента С — числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему(включая нулевой набор). Переведите полученную двоичную запись значений функции X в десятичную систему счисления.

Решение.

Запишем уравнение, используя более простые обозначения операций:

1) это выражение с тремя переменными, поэтому в таблице истинности будет строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр

2) переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел

3) вряд ли вы сможете сразу написать значения функции Х для каждой комбинации, поэтому удобно добавить в таблицу дополнительные столбцы для расчета промежуточных результатов (см. таблицу ниже)

X 0

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

4) заполняем столбцы таблицы:

А	В	С					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

значение равно 1 только в тех строчках, где А = В

значение равно 1 в тех строчках, где либо В либо С = 1

значение равно 0 только в тех строчках, где А = 1 и В + С = 0

значение — это инверсия предыдущего столбца (0 заменяется на 1, а 1 – на 0)

результат Х (последний столбец) — это логическая сумма двух столбцов и

5) чтобы получить ответ, выписываем биты из столбца Х сверху вниз:

6) переводим это число в десятичную систему:

Ответ: 171

Каково наибольшее целое число X, при котором истинно высказывание (10 (X+1)·(X+2))?

Решение.

Уравнение является операцией импликации между двумя отношениями:

1) Конечно, здесь можно применить тот же способ, что и в примере 2208, однако при этом понадобится решать квадратные уравнения (не хочется…);

2) Заметим, что по условию нас интересуют только целые числа, поэтому можно попытаться как─то преобразовать исходное выражение, получив равносильное высказывание (точные значения корней нас совершенно не интересуют!);

3) Рассмотрим неравенство : очевидно, что может быть как положительным, так и отрицательным числом;

4) Легко проверить, что в области высказывание истинно при всех целых , а в области — при всех целых (чтобы не запутаться, удобнее использовать нестрогие неравенства, и , вместо и );

5) Поэтому для целых можно заменить на равносильное выражение

6) область истинности выражения — объединение двух бесконечных интервалов;

7) Теперь рассмотрим второе неравенство : очевидно, что так же может быть как положительным, так и отрицательным числом;

8) В области высказывание истинно при всех целых , а в области — при всех целых , поэтому для целых можно заменить на равносильное выражение

9) область истинности выражения — закрытый интервал;

10) Заданное выражение истинно везде, кроме областей, где и ;

11) Обратите внимание, что значение уже не подходит, потому что там и , то есть импликация дает 0;

12) При подставлении 2, (10 (2+1) · (2+2)), или 0 → 0 что удовлетворяет условию.

Таким образом, ответ 2.

Ответ: 2

Каково наибольшее целое число X, при котором истинно высказывание

(50 (X+1)·(X+1))?

Решение.

Применим преобразование импликации и преобразуем выражение:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Логическое ИЛИ истинно когда истинно хотя бы одно логическое высказывание. Решив оба неравенства и учитывая, что видим, что наибольшее целое число, при котором выполняется хотя бы одно из них - 7 (на рисунке жёлтым изображено положительное решение второго неравенства, синим - первого).

Ответ: 7

Укажите значения переменных К, L, M, N, при которых логическое выражение

(¬(М ∨ L) ∧ К) → (¬К ∧ ¬М ∨ N)

ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.

Решение.

Дублирует задание 3584.

Ответ: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Решение.

Применим преобразование импликации:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Применим отрицание к обоим частям уравнения:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Преобразуем:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Следовательно, M = 0, N = 0, рассмотрим теперь (¬K ∧ L ∨ M ∧ L):

из того, что M = 0, N = 0 следует, что M ∧ L = 0, тогда ¬K ∧ L = 1, то есть K = 0, L = 1.

Ответ: 0100

Укажите значения переменных K, L, M, N, при которых логическое выражение

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Решение.

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

1) из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных

2) из таблицы истинности операции «импликация» следует, что это выражение ложно тогда и только тогда, когда одновременно

3) первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда и ; отсюда следует (логическая сумма равна нулю), что может быть только при ; таким образом, три переменных мы уже определили

4) из второго условия, , при и получаем .

Дублирует задание

Ответ: 1000

Укажите значения логических переменных Р, Q, S, Т, при которых логическое выражение

(Р ∨ ¬Q) ∨ (Q → (S ∨ Т)) ложно.

Ответ запишите в виде строки из четырех символов: значений переменных Р, Q, S, T (в указанном порядке).

Решение.

(1) (Р ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Применим преобразование импликации:

¬Q ∨ S ∨ Т = 0 => S = 0, T = 0.

Ответ: 0100

Укажите значения переменных K, L, M, N, при которых логическое выражение

(K → M) ∨ (L ∧ K) ∨ ¬N

ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Решение.

Логическое "ИЛИ" ложно тогда и только тогда, когда ложны оба утверждения.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Применим преобразование импликации для первого выражения:

¬K ∨ M = 0 => K = 1, M = 0.

Рассмотрим второе выражение:

(L ∧ K) ∨ ¬N = 0 (см. результат первого выражения) => L ∨ ¬N = 0 => L = 0, N = 1.

Ответ: 1001.

Ответ: 1001

Укажите значения переменных K, L, M, N, при которых логическое выражение

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

истинно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Решение.

Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.

1) (K → M) = 1 Применим преобразование импликации: ¬K ∨ M = 1

2) (K → ¬M) = 1 Применим преобразование импликации: ¬K ∨ ¬M = 1

Отсюда следует, что K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Применим преобразование импликации: K ∨ (M ∧ ¬L ∧ N) = 1 из того что K = 0 получаем.

Как решать некоторые задачи разделов A и B экзамена по информатике

Урок №3. Логика. Логические функции. Решение уравнений

Большое количество задач ЕГЭ посвящено логике высказываний. Для решения большинства из них достаточно знания основных законов логики высказываний, знания таблиц истинности логических функций одной и двух переменных. Приведу основные законы логики высказываний.

1. Коммутативность дизъюнкции и конъюнкции:
   a ˅ b ≡ b ˅ a
   a ^ b ≡ b ^ a
2. Дистрибутивный закон относительно дизъюнкции и конъюнкции:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ с) ≡ (a ^ b) ˅ (a ^ с)
3. Отрицание отрицания:
   ¬(¬а) ≡ а
4. Непротиворечивость:
   a ^ ¬а ≡ false
5. Исключающее третье:
   a ˅ ¬а ≡ true
6. Законы де-Моргана:
   ¬(а ˅ b) ≡ ¬а ˄ ¬b
   ¬(а ˄ b) ≡ ¬а ˅ ¬b
7. Упрощение:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ true ≡ a
   a ˄ false ≡ false
8. Поглощение:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Замена импликации
   a → b ≡ ¬a ˅ b
10. Замена тождества
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Представление логических функций

Любую логическую функцию от n переменных – F(x 1 , x 2 , … x n) можно задать таблицей истинности. Такая таблица содержит 2 n наборов переменных, для каждого из которых задается значение функции на этом наборе. Такой способ хорош, когда число переменных относительно невелико. Уже при n > 5 представление становится плохо обозримым.

Другой способ состоит в том, чтобы задавать функцию некоторой формулой, используя известные достаточно простые функции. Система функций {f 1 , f 2 , … f k } называется полной, если любую логическую функцию можно выразить формулой, содержащей только функции f i .

Полной является система функций {¬, ˄, ˅}. Законы 9 и 10 являются примерами, демонстрирующими, как импликация и тождество выражается через отрицание, конъюнкцию и дизъюнкцию.

Фактически полной является и система из двух функций – отрицания и конъюнкции или отрицания и дизъюнкции. Из законов де-Моргана следуют представления, позволяющие выразить конъюнкцию через отрицание и дизъюнкцию и соответственно выразить дизъюнкцию через отрицание и конъюнкцию:

(а ˅ b) ≡ ¬(¬а ˄ ¬b)
(а ˄ b) ≡ ¬(¬а ˅ ¬b)

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

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

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

Задача 15:

Дан фрагмент таблицы истинности. Какая из трех приведенных функций соответствует этому фрагменту?

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Функция под номером 3.

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

Задача 16:

Какое из приведенных чисел удовлетворяет условию:

(цифры, начиная со старшего разряда, идут в порядке убывания) → (число — четное) ˄ (младшая цифра – четная) ˄ (старшая цифра – нечетная)

Если таких чисел несколько, укажите наибольшее.

1. 13579
2. 97531
3. 24678
4. 15386

Условию удовлетворяет число под номером 4.

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

Задача 17: Два свидетеля дали следующие показания:

Первый свидетель: Если А виновен, то В и подавно виновен, а С – невиновен.

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

Какие заключения о виновности А, В и С можно сделать на основании свидетельских показаний?

Ответ: Из свидетельских показаний следует, что А и В виновны, а С – невиновен.

Решение: Конечно, ответ можно дать, основываясь на здравом смысле. Но давайте рассмотрим, как это можно сделать строго и формально.

Первое, что нужно сделать – это формализовать высказывания. Введем три логические переменные — А, В и С, каждая из которых имеет значение true (1), если соответствующий подозреваемый виновен. Тогда показания первого свидетеля задаются формулой:

A → (B ˄ ¬C)

Показания второго свидетеля задаются формулой:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

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

Построим таблицу истинности для этих показаний:

A	B	C	F 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Суммарные свидетельские показания истинны только в одном случае, приводящие к однозначному ответу – А и В виновны, а С – невиновен.

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

Логические уравнения и системы уравнений

Пусть F(x 1 , x 2 , …x n) – логическая функция от n переменных. Логическое уравнение имеет вид:

F(x 1 , x 2 , …x n) = С,

Константа С имеет значение 1 или 0.

Логическое уравнение может иметь от 0 до 2 n различных решений. Если С равно 1, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (1). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида:

F(x 1 , x 2 , …x n) = 1

Действительно, пусть задано уравнение:

F(x 1 , x 2 , …x n) = 0

В этом случае можно перейти к эквивалентному уравнению:

¬F(x 1 , x 2 , …x n) = 1

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

F 1 (x 1 , x 2 , …x n) = 1

F 2 (x 1 , x 2 , …x n) = 1

F k (x 1 , x 2 , …x n) = 1

Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций F:

Ф = F 1 ˄ F 2 ˄ … F k

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

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

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

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

Задача 18

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют системе из двух уравнений?

Ответ: Система имеет 36 различных решений.

Решение: Система уравнений включает два уравнения. Найдем число решений для первого уравнения, зависящего от 5 переменных – x 1 , x 2 , …x 5 . Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, — конъюнкцию условий можно рассматривать как систему уравнений.

Построим дерево решений для импликации (x1→ x2) — первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева:

Дерево состоит из двух уровней по числу переменных уравнения. Первый уровень описывает первую переменную X 1 . Две ветви этого уровня отражают возможные значения этой переменной – 1 и 0. На втором уровне ветви дерева отражают только те возможные значения переменной X 2 , для которых уравнение принимает значение истина. Поскольку уравнение задает импликацию, то ветвь, на которой X 1 имеет значение 1, требует, чтобы на этой ветви X 2 имело значение 1. Ветвь, на которой X 1 имеет значение 0, порождает две ветви со значениями X 2 , равными 0 и 1. Построенное дерево задает три решения, на которых импликация X 1 → X 2 принимает значение 1. На каждой ветви выписан соответствующий набор значений переменных, дающий решение уравнения.

Вот эти наборы: {(1, 1), (0, 1), (0, 0)}

Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию X 2 → X 3 . Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная X 2 уже имеет значения на дереве, то на всех ветвях, где переменная X 2 имеет значение 1, переменная X 3 также будет иметь значение 1. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная X 2 имеет значение 0, даст разветвление на две ветви, где переменная X 3 получит значения 0 и 1. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение. Исходное первое уравнение:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения:

Второе уравнение нашей системы аналогично первому:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных X i может быть скомбинировано с каждым решением для переменных Y j , то общее число решений равно 36.

Заметьте, построенное дерево решений дает не только число решений (по числу ветвей), но и сами решения, выписанные на каждой ветви дерева.

Задача 19

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→y1) = 1

Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y.

Из уравнения X 1 → Y 1 следует, что когда X 1 имеет значение 1(одно такое решение существует), то и Y 1 имеет значение 1. Таким образом, существует один набор, на котором X 1 и Y 1 имеют значения 1. При X 1 , равном 0, Y 1 может иметь любое значение, как 0, так и 1. Поэтому каждому набору с X 1 , равном 0, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 31.

Задача 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Решение: Вспоминания основные эквивалентности, запишем наше уравнение в виде:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Циклическая цепочка импликаций означает тождественность переменных, так что наше уравнение эквивалентно уравнению:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Это уравнение имеет два решения, когда все X i равны либо 1, либо 0.

Задача 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Решение: Так же, как и в задаче 20, от циклических импликаций перейдем к тождествам, переписав уравнение в виде:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Построим дерево решений для этого уравнения:

Задача 22

Сколько решений имеет следующая система уравнений?

((X 1 ≡ X 2) ˄ (X 3 ≡ X 4)) ˅(¬(X 1 ≡ X 2) ˄ ¬(X 3 ≡ X 4)) = 0

((X 3 ≡ X 4) ˄ (X 5 ≡ X 6)) ˅(¬(X 3 ≡ X 4) ˄ ¬(X 5 ≡ X 6)) = 0

((X 5 ≡ X 6) ˄ (X 7 ≡ X 8)) ˅(¬(X 5 ≡ X 6) ˄ ¬(X 7 ≡ X 8)) = 0

((X 7 ≡ X 8) ˄ (X 9 ≡ X 10)) ˅(¬(X 7 ≡ X 8) ˄ ¬(X 9 ≡ X 10)) = 0

Ответ: 64

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

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Тогда первое уравнение примет вид:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Уравнение можно упростить, записав его в виде:

(Y 1 ≡ Y 2) = 0

Переходя к традиционной форме, запишем систему после упрощений в виде:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Дерево решений для этой системы простое и состоит из двух ветвей с чередующимися значениями переменных:

Возвращаясь к исходным переменным X, заметим, что каждому значению переменной Y соответствует 2 значения переменных X, поэтому каждое решение в переменных Yпорождает 2 5 решений в переменных X. Две ветви порождают 2 * 2 5 решений, так что общее число решений равно 64.

Как видите, каждая задача на решение системы уравнений требует своего подхода. Общим приемом является выполнение эквивалентных преобразований для упрощения уравнений. Общим приемом является и построение деревьев решений. Применяемый подход частично напоминает построение таблицы истинности с той особенностью, что строятся не все наборы возможных значений переменных, а лишь те, на которых функция принимает значение 1 (истина). Часто в предлагаемых задачах нет необходимости в построении полного дерева решений, поскольку уже на начальном этапе удается установить закономерность появления новых ветвей на каждом следующем уровне, как это сделано, например, в задаче 18.

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

Если задачу трудно решить вручную, то можно поручить решение задачи компьютеру, написав соответствующую программу решения уравнений и систем уравнений.

Написать такую программу несложно. Такая программа легко справится со всеми задачами, предлагаемыми в ЕГЭ.

Как это ни странно, но задача нахождения решений систем логических уравнений является сложной и для компьютера, оказывается и у компьютера есть свои пределы. Компьютер может достаточно просто справиться с задачами, где число переменных 20 -30, но начнет надолго задумываться на задачах большего размера. Дело в том, что функция 2 n , задающая число наборов, является экспонентой, быстро растущей с увеличением n. Настолько быстро, что обычный персональный компьютер за сутки не справится с задачей, у которой 40 переменных.

Программа на языке C# для решения логических уравнений

Написать программу для решения логических уравнений полезно по многим причинам, хотя бы потому, что с ее помощью можно проверять правильность собственного решения тестовых задач ЕГЭ. Другая причина в том, что такая программа является прекрасным примером задачи на программирование, соответствующей требованиям, предъявляемым к задачам категории С в ЕГЭ.

Идея построения программы проста, — она основана на полном переборе всех возможных наборов значений переменных. Поскольку для заданного логического уравнения или системы уравнений число переменных n известно, то известно и число наборов – 2 n , которые требуется перебрать. Используя базовые функции языка C# — отрицание, дизъюнкцию, конъюнкцию и тождество, нетрудно написать программу, которая для заданного набора переменных вычисляет значение логической функции, соответствующей логическому уравнению или системе уравнений.

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

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

Вот как выглядит функция на языке C#, решающая нашу задачу:

///

/// программа подсчета числа решений

/// логического уравнения (системы уравнений)

///

///

/// логическая функция — метод,

/// сигнатура которого задается делегатом DF

///

/// число переменных

/// число решений

static int SolveEquations(DF fun, int n)

bool set = new bool[n];

int m = (int)Math.Pow(2, n); //число наборов

int p = 0, q = 0, k = 0;

//Полный перебор по числу наборов

for (int i = 0; i < m; i++)

//Формирование очередного набора — set,

//заданного двоичным представлением числа i

for (int j = 0; j < n; j++)

k = (int)Math.Pow(2, j);

//Вычисление значения функции на наборе set

Для понимания программы, надеюсь, достаточно сделанных объяснений идеи программы и комментариев в ее тексте. Остановлюсь лишь на пояснении заголовка приведенной функции. У функции SolveEquations два входных параметра. Параметр fun задает логическую функцию, соответствующую решаемому уравнению или системе уравнений. Параметр n задает число переменных функции fun. В качестве результата функция SolveEquations возвращает число решений логической функции, то есть число тех наборов, на которых функция принимает значение true.

Для школьников привычно, когда у некоторой функции F(x) входным параметром x является переменная арифметического, строкового или логического типа. В нашем случае используется более мощная конструкция. Функция SolveEquations относится к функциям высшего порядка – функциям типа F(f), у которых параметрами могут быть не только простые переменные, но и функции.

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

delegate bool DF(bool vars);

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

В заключение приведу программу, в которой функция SolveEquations используется для решения нескольких систем логических уравнений. Функция SolveEquations является частью приводимого ниже класса ProgramCommon:

class ProgramCommon

delegate bool DF(bool vars);

static void Main(string args)

Console.WriteLine(«У Функции And решений — » +

SolveEquations(FunAnd, 2));

Console.WriteLine(«У Функции 51 решений — » +

SolveEquations(Fun51, 5));

Console.WriteLine(«У Функции 53 решений — » +

SolveEquations(Fun53, 10));

static bool FunAnd(bool vars)

return vars && vars;

static bool Fun51(bool vars)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

static bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Вот как выглядят результаты решения по этой программе:

10 задач для самостоятельной работы

1. Какие из трех функций эквивалентны:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. Дан фрагмент таблицы истинности:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Какой из трех функций соответствует этот фрагмент:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. В состав жюри входят три человека. Решение принимается, если за него голосует председатель жюри, поддержанный хотя бы одним из членов жюри. В противном случае решение не принимается. Постройте логическую функцию, формализующую процесс принятия решения.
5. X выигрывает у Y, если при четырех бросаниях монеты трижды выпадает «орёл». Задайте логическую функцию, описывающую выигрыш X.
6. Слова в предложении нумеруются, начиная с единицы. Предложение считается правильно построенным, если выполняются следующие правила:
   1. Если четное в нумерации слово заканчивается на гласную, то следующее слово, если оно существует, должно начинаться с гласной.
   2. Если нечетное в нумерации слово заканчивается согласной, то следующее слово, если оно существует, должно начинаться с согласной и заканчиваться гласной.
      Какие из следующих предложений правильно построены:
   3. Мама мыла Машу мылом.
   4. Лидер всегда является образцом.
   5. Правда хорошо, а счастье лучше.
7. Сколько решений имеет уравнение:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Перечислите все решения уравнения:
   (a → b) → c = 0
9. Сколько решений имеет следующая система уравнений:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Сколько решений имеет уравнение:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Ответы к задачам:

1. Эквивалентными являются функции b и c.
2. Фрагмент соответствует функции b.
3. Пусть логическая переменная P принимает значение 1, когда председатель жюри голосует «за» принятие решения. Переменные M 1 и M 2 представляют мнение членов жюри. Логическая функция, задающая принятие положительного решения может быть записана так:
   P ˄ (M 1 ˅ M 2)
4. Пусть логическая переменная P i принимает значение 1, когда при i-м бросании монеты выпадает «орёл». Логическая функция, задающая выигрыш X может быть записана так:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Предложение b.
6. Уравнение имеет 3 решения: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

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

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

Пример 1.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

				Кол-во наборов на x1…x8

Сло­жим ко­ли­че­ство наборов: 1 + 3 + 9 + 27 + 81 = 121.

Ответ: 121

Пример 2.

Сколько существует различных наборов значений логических переменных x1, x2, ... x9, y1, y2, ... y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ... x9, y1, y2, ... y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение:

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 - два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.

Ответ: 1024

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

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

Пример 3.

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

¬x9 ∨ x10 = 1,

где x1, x2, … x10 - ло­ги­че­ские пе­ре­мен­ные?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний x1, x2, … x10, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 (0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 (0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

N i +1 = N i + 1. Тогда для десяти переменных получим 11 наборов.

Ответ: 11

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

Пример 4.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 , ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

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

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

Аналогично, решениями второго и третьего уравнений будут абсолютно такие же наборы y1,…,y4 и z1,…, z4.

Теперь проанализируем четвертое уравнение системы: x 4 ∧ y 4 ∧ z 4 = 0. Решением будут все наборы x4, y4, z4, в которых хотя бы одна из переменных равна 0.

Т.е. для x4 = 0 подойдут все возможные наборы (y4, z4), а для x4 = 1 подойдут наборы (y4, z4), в которых присутствует хотя бы один ноль: (0, 0), (0,1) , (1,0).

				Кол-во наборов

Общее количество наборов 25 + 4*9 = 25 + 36 = 61.

Ответ: 61

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

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

Пример 5.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x7, y1, y2, … y7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, ..., x7, y1, y2, ..., y7, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

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

Обозначим:

число наборов (0,0) на переменных (x1,y1) через A 1 ,

число наборов (0,1) на переменных (x1,y1) через B 1 ,

число наборов (1,0) на переменных (x1,y1) через C 1 ,

число наборов (1,1) на переменных (x1,y1) через D 1 .

число наборов (0,0) на переменных (x2,y2) через A 2 ,

число наборов (0,1) на переменных (x2,y2) через B 2 ,

число наборов (1,0) на переменных (x2,y2) через C 2 ,

число наборов (1,1) на переменных (x2,y2) через D 2 .

Из дерева решений видим, что

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

Заметим, что набор (0,0) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. A 2 =B 1 +C 1 +D 1 .

Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B 2 =B 1 +C 1 +D 1 .

Аналогично рассуждая, заметим, что С 2 =B 1 +C 1 +D 1 . D 2 = D 1 .

Таким образом, получаем рекуррентные формулы:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

Составим таблицу

Наборы	Обозн .	Формула	Количество наборов
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	A i	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	B i	B i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A 7 .

Тогда общее количество наборов равно B 7 + C 7 + D 7 = 127+127+1 = 255

Ответ: 255

Размер: px

Начинать показ со страницы:

Транскрипт

1 Решение логических уравнений и систем логических уравнений Пусть F(x, x2, xn) логическая функция от n переменных. Логическое уравнение имеет вид: F(x, x2, xn) = С, где константа С имеет значение или. Логическое уравнение может иметь от до 2 n различных решений. Если С равно, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида: F(x, x2, xn) = Действительно, пусть задано уравнение: F(x, x2, xn) = В этом случае можно перейти к эквивалентному уравнению: F(x, x2, xn) = Рассмотрим систему из k логических уравнений: F(x, x2, xn) = F2(x, x2, xn) = { Fk(x, x2, xn) = Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций F: Ф = F F2 Fk Если число переменных невелико, например, менее 5, то нетрудно построить таблицу истинности для функции Ф, что позволяет сказать, сколько решений имеет система и каковы наборы, дающие решения. В некоторых задачах ЕГЭ по нахождению решений системы логических уравнений число переменных доходит до значения. Тогда построить таблицу истинности становится практически неразрешимой задачей. Для решения задачи требуется другой подход. Для произвольной системы уравнений не существует общего способа, отличного от перебора, позволяющего решать такие задачи. В предлагаемых на экзамене задачах решение обычно основано на учете специфики системы уравнений. Однако, повторю, что кроме перебора всех вариантов набора переменных, общего способа решения задачи нет. Решение нужно строить исходя из представленной системы. Часто полезно провести предварительное упрощение системы уравнений, используя известные законы логики. Другой полезный прием решения этой задачи состоит в следующем. Нам интересны не все наборы, а только те, на которых функция Ф имеет значение. Вместо построения полной таблицы истинности будем строить ее аналог - бинарное дерево решений. Каждая ветвь этого дерева соответствует

2 одному решению и задает набор, на котором функция Ф имеет значение. Число ветвей в дереве решений совпадает с числом решений системы уравнений. Что такое бинарное дерево решений и как оно строится, поясню на примерах нескольких задач. Задача Сколько существует различных наборов значений логических переменных x, x2, x3, x4, x5, y, y2, y3, y4, y5, которые удовлетворяют системе из двух уравнений? (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = { (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Ответ: Система имеет 36 различных решений. Система уравнений включает два уравнения. Найдем число решений для первого уравнения, зависящего от 5 переменных x, x2, x5. Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, - конъюнкцию условий можно рассматривать как систему уравнений. Построим дерево решений для импликации (x x2) - первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева: X X2 Дерево состоит из двух уровней по числу переменных уравнения. Первый уровень описывает первую переменную X. Две ветви этого уровня отражают возможные значения этой переменной и. На втором уровне ветви дерева отражают только те возможные значения переменной X2, для которых уравнение принимает значение истина. Поскольку уравнение задает импликацию, то ветвь, на которой X имеет значение, требует, чтобы на этой ветви X2 имело значение. Ветвь, на которой X имеет значение, порождает две ветви со значениями X2, равными и. Построенное дерево задает три решения, на которых импликация X X2 принимает значение. На каждой ветви выписан соответствующий набор значений переменных, дающий решение уравнения. Вот эти наборы: {(,), (,), (,)} Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию X2 X3. Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная X2 уже имеет значения на дереве, то на всех ветвях, где переменная X2 имеет значение, переменная X3 также будет иметь значение. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная X2 имеет значение, даст разветвление на две ветви, где переменная X3 получит значения и. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение.

3 Исходное первое уравнение: (x x2) /\ (x2 x3) /\ (x3 x4) /\ (x4 x5) = имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения: X X2 X3 X4 X5 Второе уравнение нашей системы аналогично первому: (y y2) /\ (y2 y3) /\ (y3 y4) /\ (y4 y5) = Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных Xi может быть скомбинировано с каждым решением для переменных Yj, то общее число решений равно 36. Заметьте, построенное дерево решений дает не только число решений (по числу ветвей), но и сами решения, выписанные на каждой ветви дерева. Задача 2 Сколько существует различных наборов значений логических переменных x, x2, x3, x4, x5, y, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям? (x x2) ^ (x2 x3) ^ (x3 x4) ^ (x4 x5) = {(y y2) ^ (y2 y3) ^ (y3 y4) ^ (y4 y5) = (x y) = Ответ: 3 Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y. Из уравнения X Y следует, что когда X имеет значение (одно такое решение существует), то и Y имеет значение. Таким образом, существует один набор, на котором

4 X и Y имеют значения. При X, равном, Y может иметь любое значение, как, так и. Поэтому каждому набору с X, равном, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 3. Задача 3 Сколько решений имеет уравнение: (X X2) (X2 X3) (X3 X4) (X4 X5) (X5 X) = Ответ: 2 Вспоминания основные эквивалентности, запишем наше уравнение в виде: (X X2) (X2 X3) (X3 X4) (X4 X5) (X5 X) = Циклическая цепочка импликаций означает тождественность переменных, так что наше уравнение эквивалентно уравнению: X X2 X3 X4 X5 = Это уравнение имеет два решения, когда все Xi равны либо, либо. Задача 4 Сколько решений имеет уравнение: (X X2) (X2 X3) (X3 X4) (X4 X2) (X4 X5) = Ответ: 4 Так же, как и в задаче 2, от циклических импликаций перейдем к тождествам, переписав уравнение в виде: (X X2) (X2 X3 X4) (X4 X5) = Построим дерево решений для этого уравнения: X X2 X3 X4 X5

5 Задача 4 Сколько решений имеет следующая система уравнений? Ответ: 64 ((X X2) (X3 X4)) ((X X2) (X3 X4)) = ((X3 X4) (X5 X6)) ((X3 X4) (X5 X6)) = ((X5 X6) (X7 X8)) ((X5 X6) (X7 X8)) = {((X7 X8) (X9 X)) ((X7 X8) (X9 X)) = Перейдем от переменных к 5 переменным, введя следующую замену переменных: Y = (X X2); Y2 = (X3 X4); Y3 = (X5 X6); Y4 = (X7 X8); Y5 = (X9 X); Тогда первое уравнение примет вид: (Y Y2) (Y Y2) = Уравнение можно упростить, записав его в виде: (Y Y2) = Переходя к традиционной форме, запишем систему после упрощений в виде: (Y Y2) = (Y2 Y3) = { (Y3 Y4) = (Y4 Y5) = Дерево решений для этой системы простое и состоит из двух ветвей с чередующимися значениями переменных: Y Y2 Y3 Y4 Y5 Возвращаясь к исходным переменным X, заметим, что каждому значению переменной Y соответствует 2 значения переменных X, поэтому каждое решение в переменных Yпорождает 2 5 решений в переменных X. Две ветви порождают 2 * 2 5 решений, так что общее число решений равно 64. Как видите, каждая задача на решение системы уравнений требует своего подхода. Общим приемом является выполнение эквивалентных преобразований для упрощения уравнений.

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

Путилов Виктор Васильевич МАОУ СОШ 46 Системы логических уравнений. Оглавление Замечание о замене переменных.... Задачи содержащие импликацию или ее эквивалентную запись....2 Наличие дополнительного условия...6

Решение системы логических уравнений. Сколько решений имеет уравнение A BB C C D = 0 Количество наборов переменных равно =. Можно составить таблицу истинности и проверить, сколько наборов соответствуют

Построение и анализ таблиц истинности логических выражений. ЕГЭ 2015 2 (базовый уровень, время 3 мин) Пример Р-13. Каждое логическое выражение A и B зависит от одного и того же набора из 5 переменных.

Н Б Рогов Как научиться решать задание B15 ЕГЭ по информатике (системы логических уравнений) за 180+ минут Материалы для занятий Раздел в сети: http://basicschoolru/?page=eam_info_b15 Теоретическое введение:

B4 Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,), неудобны, интуитивно непонятны

Математика и математическое моделирование УДК 004.023 Семенов Сергей Максимович Владивостокский государственный университет экономики и сервиса Россия. Владивосток Об одном способе решения систем логических

B4 (высокий уровень, время 1 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,),

B0 (высокий уровень, время 0 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,),

19022017 Битовые операции в задачах КИМ ЕГЭ по информатике Часть II КЮ Поляков, дтн, учитель информатики ГБОУ СОШ 163, г Санкт-Петербург В данной статье рассматриваются задачи следующего типа впервые эти

Самостоятельная работа по теме «Способы задания логических функций» 1. Вычислить значение функции F(x, y, z) = на наборе переменных (1, 1, 0). 3. Определить эквивалентность функций F(x, y, z) = и G(x,

Логика это наука, изучающая методы установления истинности или ложности одних высказываний на основе истинности или ложности других высказываний. Высказывание (суждение) некоторое предложение, которое

B высокий уровень, время 0 мин) К. Поляков, 009-0 Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Задача 1: Дан фрагмент таблицы истинности выражения F: Каким выражением может быть F? X Y Z F 0 0 0 0 0 0 1 0 1 1 1 1 1) X /\ Y /\ Z 2) X \/ Y \/ Z 3) X \/ Y \/ Z 4) X /\ Y /\ Z Рассмотрим первое выражение

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ (продолжение) Число булевых функций от n переменных находится по формуле: P2 (n) = 2 2n Логических функций двух переменных 6 Наиболее часто употребляются следующие функции: f (x,

Решения задач по двузначной логике Ф.Г. Кораблев Задача 1. Для функции f(x, y, z) = ((x y) (x z)) (z x) найти существенные и фиктивные переменные, произвести операцию исключения фиктивных переменных. Решение.

051216 Битовые операции в задачах КИМ ЕГЭ по информатике Часть II КЮ Поляков, дтн, учитель информатики ГБОУ СОШ 163, г Санкт-Петербург В данной статье рассматриваются задачи следующего типа впервые эти

Мирончик Е.А., учитель информатики, г. Новокузнецк Решение задания ЕГЭ-18 с битовыми операциями Описанный метод демонстрирует способ решения на основе тождественных переходов, т.е. знак равно «работает»

Тема: Основные понятия математической логики. Примерные вопросы Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,), неудобны, интуитивно

Часть 1 1. Укажите, какое логическое выражение равносильно выражению A /\ (B \/ C). 1) A \/ B \/ C 2) A /\ B /\ C 3) A /\ B /\ C 4) A /\ B /\ C Решение: Применяя формулу де Моргана (B \/ C) = B /\ C и

Глинка Н.В. Используемые обозначения Отрицание Умножение (конъюнкция) Сложение (дизъюнкция) Импликация Эквивалентность Примеры задач до 2010 учебного года Сколько различных решений имеет уравнение ((K

Битовые операции в задачах КИМ по информатике Типы задач В данном вебинаре рассматриваются задачи следующего типа (впервые эти задачи появились в КИМ на ЕГЭ 2015 года): Введжм выражение M & K, обозначающее

Практическая работа 6 Решение логических задач с применением законов алгебры логики Цель работы: закрепление умений преобразовывать логические выражения с использованием законов алгебры логики, вычислять

A10 (базовый уровень, время 1 мин) Тема: Преобразование логических выражений. Формулы де Моргана. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Гурская К.А., Ивин В.В., Семёнов С.М. Решение задач математической логики в ЕГЭ по информатике 1 УДК 004.9 Гурская К.А., Ивин В.В., Семёнов С.М. Учебное пособие «Решение задач математической логики в ЕГЭ

ОГЛАВЛЕНИЕ Предисловие............................. 3 Глава 1. Математическая логика................. 4 1. Алгебра высказываний.................. 4 2. Булевы алгебры...................... 12 3. Исчисление

ЛЕКЦИЯ 5 ЛОГИЧЕСКИЕ ОПЕРАЦИИ В ИНФОРМАТИКЕ 1. Математическая логика и информатика 2. Логические выражения и логические операции 3. Построение таблиц истинности и логических функций 4. Законы логики и правила

B5 высокий уровень, время 0 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике,), неудобны,

Алгебра логики Алгебра логики формальная логическая теория, раздел математической логики, разработанный в XIX веке английским математиком Джорджем Булем. В алгебре логики используются алгебраические методы

2 (базовый уровень, время мин) Тема: Построение и анализ таблиц истинности логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

A8 (базовый уровень, время 1 мин) Тема: Преобразование логических выражений. Формулы де Моргана. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

B15 Укажите значения переменных K, L, M, N, при которых логическое выражение (K M) (L K) N ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке).

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

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

Муниципальное бюджетное общеобразовательное учреждение города Абакана «Средняя общеобразовательная школа 11» Методическая разработка по теме Решение заданий типа 18 ЕГЭ по информатике Атюшкина Марина Валерьевна,

Тема 4. Логические основы ЭВМ 1.ОСНОВНЫЕ СВЕДЕНИЯ ИЗ АЛГЕБРЫ ЛОГИКИ... 1 2. ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ... 4 3. ПОНЯТИЕ О МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ... 6 4.ТЕХНИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ...

Тема 9. Логические основы ЭВМ. 1. Логика. Информация, обрабатываемая в ЭВМ, представляется с помощью физических величин, которые могут принимать только два устойчивых состояния и называются «двоичные переменные».

Иррациональные неравенства Неравенства, в которых переменная содержится под знаком корня, называются иррациональными Основным методом решения иррациональных неравенств является метод сведения исходного

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

Краевой конкурс учебно-исследовательских и проектных работ учащихся «Прикладные вопросы математики» Алгебра Алгебра логики Семушева Алена Сергеевна, МОУ «Лицей» г. Перми, кл. Боркова Ольга Владимировн,

К. Поляков, 009-0 B5 высокий уровень, время 0 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 1 Линейные уравнения первого порядка, уравнение Бернулли Уравнение в полных дифференциалах Линейным дифференциальным уравнением первого порядка называется уравнение + p(= q(Если

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ ÄÈÑÊÐÅÒÍÀß ÌÀÒÅÌÀÒÈÊÀ

A9 (базовый уровень, время 2 мин) Тема: Построение таблиц истинности логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Мирончик Е.А., МБ НОУ «Лицей», г. Новокузнецк Метод отображения Задание. Сколько решений имеет система: Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено три переменных. Зная

Федеральное агентство по образованию Уральский государственный экономический университет Ю. Б. Мельников Булевы и логические функции Раздел электронного учебника для сопровождения лекции e-mail: [email protected],

Е.В.Просолупов 42. Булева алгебра. Функции алгебры логики 1 Булевы функции Будем рассматривать булевы функции функции, аргументы и значения которых принимают значения истина и ложь. Истину и ложь будем

Федеральное агентство по образованию Уральский государственный экономический университет Ю. Б. Мельников Булевы и логические функции Раздел электронного учебника для сопровождения лекции Изд. 3-е, испр.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное автономное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

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

Говорят, что когда Аристотель придумал логику, он на радостях устроил пир и велел заколоть 40 баранов. С тех пор бараны логику не любят. Основные понятия алгебры логики 10 класс, 2017-2018 учебный год

Дифференциальные уравнения первого порядка разрешенные относительно производной Теорема существования и единственности решения В общем случае дифференциальное уравнение первого порядка имеет вид F ()

Лекция 2. Конъюнктивные нормальные формы. Имплицента, простая имплицента функции. Сокращенная КНФ функции алгебры логики. Способы построения сокращенной КНФ. Лектор Селезнева Светлана Николаевна [email protected]

ЛОГИКА ВЫСКАЗЫВАНИЙ Высказывания Высказывание повествовательное предложение, содержание которого можно оценить либо как истинное, либо как ложное. Различают: абсолютно истинные высказывания, абсолютно

Доля П.Г. Харьковский Национальный Университет механико математический факультет Дискретная математика. Конспект лекций. Оглавление 1. Алгебра высказываний и логика. 1.1 Высказывания и логические операции...

Законы алгебры логики Это интересно! Математика и закон де Моргана Как вы запишите математически принадлежность точки x отрезку ? Это можно сделать так: 2 x 5. Это означает, что одновременно должны

Математическая логика и теория алгоритмов Первухин Михаил Александрович Логическое следствие в АВ Говорят, что формула ψ x 1, x n АВ является логическим следствием формул φ 1 (x 1, x n), φ m x 1,

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ

ЛЕКЦИЯ 21 СКОБКИ ПУАССОНА. ТЕОРЕМА ЯКОБИ-ПУАССОНА. КАНОНИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ 1. Скобки Пуассона На прошлой лекции вводилось понятие скобки Лагранжа. Это выражение было составлено из частных производных

8 задание ЕГЭ («Знание основных понятий и законов математической логики») ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ Х = Х X /\ Y = Y /\ X X \/ Y = Y \/ X (X /\ Z) \/ (Y /\ Z)=(X \/ Y) /\ Z A\/ = A A/\ = A A/\ =. ЗАКОНЫ АЛГЕБРЫ

ГЛАВА 6 Формализм скобок Пуассона в классической механике 61 Скобки Пуассона Скобки Пуассона Пусть даны две динамические величины две функции канонических переменных и времени t: (и (Скобкой Пуассона

Лабораторная работа АЛГОРИТМ БЕРЛЕКЭМПА-МЕССИ ДЛЯ НАХОЖДЕНИЯ КОЭФФИЦИЕНТОВ ОБРАТНОЙ СВЯЗИ ГЕНЕРАТОРА ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ Рассмотрим как можно восстановить полином задающий обратные связи

К.Ю. Поляков, М.А. Ройтберг Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, 0 http://kpolkov.sp.ru К.Ю. Поляков, М.А. Ройтберг, 0 http://kpolkov.sp.ru Постановка

Битовые операции в задачах КИМ ЕГЭ по информатике К.Ю. Поляков, д.т.н., учитель информатики ГБОУ СОШ 163, г. Санкт-Петербург В данной статье рассматриваются задачи следующего типа (впервые эти задачи появились

Министерство образования Российской федерации Донской государственный технический университет Кафедра «Высшая математика» Задачи по дискретной математике Ростов-на-Дону 2001 УДК 517 Составители: Баранов

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

A3 (базовый уровень, время 2 мин) Тема: Построение таблиц истинности логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической

Время выполнения 4 часа. ЛАБОРАТОРНАЯ РАБОТА 2 АЛГЕБРА ЛОГИКИ Цель работы Изучить основы алгебры логики. Задачи лабораторной работы В результате прохождения занятия студент должен: 1) знать: определения

Неравенства С С Подготовка к ЕГЭ 0 (материал для лекции для учителей 8040) Прокофьев АА aaprokof@yanderu Основные способы решения: Задачи С Решение неравенства на промежутках Упрощение неравенства и сведение

Приложение 1 ГРУППЫ, КОЛЬЦА, ПОЛЯ Для криптографии алгебра является одним из основных инструментов в теоретических исследованиях и практических построениях криптографических преобразований Поэтому в этом