Операции в порядке, в котором совершаются действия при ручном решении:
| Название операции | Алгебра логики | Python |
| 1) Инверсия | ¬A | not(A) |
| 2) Конъюнкция | A ∧ B | A and B |
| 3) Дизъюнкция | A ∨ B | A or B |
| 4) Импликация | A → B | A <= B |
| 5) Эквиваленция | A ≡ B | A == B |
НО: порядок действий для ручного решения не совпадает с порядком действий на питоне! → и ≡ на питоне выполняются первыми. Чтобы выровнять порядок, надо расставить скобки.
1 2 ручное
a ∧ b → c
2 1 порядок действий на питоне не верный!
a and b <= c
1 2 теперь порядок действия на питоне верный
(a and b) <= c
Импликация: 1 → 0 = 0, стальное = 1
Эквиваленция: если а и b одинаковые - то 1, разные - 0.
Шаблон программы для решения задания №2
print(‘x’, ‘y’, ‘z’, ‘w’) # печатаем имена переменных
# осуществляем перебор всех комбинаций значений переменных
for x in 0, 1:
for y in 0,1:
for z in 0, 1:
for w in 0, 1:
# переписываем функцию, используя замену операций
# и сравниваем с 0/1
if (< логическая функция из условия >) ==
< то, чему должна равняться функция F >:
print(x, y, z, w)
Прототипы задания №2 из ЕГЭ
1.1 Миша заполнял таблицу истинности функции
(¬x /\ ¬y) \/ (y≡z) \/ w,
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
|
|
|
|
|
(¬x /\ ¬y) \/ (y≡z) \/ w |
|
|
|
1 |
|
0 |
|
1 |
0 |
|
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
|
|
|
¬x \/ y |
|
0 |
1 |
0 |
В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.
Решение 
:
0 0 0
________ ____ __
(¬x /\ ¬y) \/ (y≡z) \/ w
w = 0 всегда
y≡z = 0 если 0≡1 или 1≡0, то есть y и z обязательно разные
(¬x /\ ¬y) = 0 при 0 /\ 1, 1 /\ 0, 0 /\ 0 или ¬1 /\ ¬0, ¬0 /\ ¬1, ¬1 /\ ¬1
|
z |
w |
у |
х |
(¬x /\ ¬y) \/ (y≡z) \/ w |
|
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
Или на Pyhton
print('x y w z')
for x in 0,1:
for y in 0,1:
for w in 0,1:
for z in 0,1:
f = (not x and not y) or (y == z) or w
if f ==0:
print(x,y,w,z)
Получим таблицу:
x y w z
0 1 0 0
1 0 0 1
1 1 0 0
0
0
0 можно всунуть только в 1 колонку - это w
0
1
0 колонка с одной единицей - z
Дальше смотрим по строкам, потому что в колонках по две единицы, их так не отличить.
Первая строка с одной 1 - единица на y. В колонке не хватает 0.
На оставшейся колонке x, проверим: в колонке две 1, не хватает 0. Строки получились такие же, как в таблице питона.
Полностью на питоне:
from itertools import product, permutations
def F(x, y, z, w):
return (not(x) and not(y)) or (y == z) or w
for p in permutations('xyzw'):
for a, b, c, d in product([0, 1], repeat=4):
table = [(d, c, 1, b, 0),
(1, 0, a, 1, 0),
(0, 0, 1, 1, 0)]
if len(table) != len(set(table)):
continue
if all(F(**dict(zip(p, row))) == row[-1] for row in table):
print(*p)
Ответ: zwyx
1.2 Миша заполнял таблицу истинности логической функции F
(x /\ y) \/ (y ≡ z) \/ w,
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
|
|
|
|
|
F |
|
1 |
|
0 |
0 |
0 |
|
|
1 |
|
0 |
0 |
|
1 |
0 |
1 |
|
0 |
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
|
|
|
F |
|
0 |
1 |
0 |
В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.
Решение:
...
print('x y w z')
for x in 0,1:
for y in 0,1:
for w in 0,1:
for z in 0,1:
f = (x and y) or (y == z) or w
if f ==0:
print(x,y,w,z)
Полностью на питоне:
from itertools import product, permutations
def F(x, y, z, w):
return (x and y) or (y == z) or w
for p in permutations('xyzw'):
for a, b, c, d in product([0, 1], repeat=4):
table = [(1, b, 0, 0, 0),
(a, 1, c, 0, 0),
(1, 0, 1, d, 0)]
if len(table) != len(set(table)):
continue
if all(F(**dict(zip(p, row))) == row[-1] for row in table):
print(*p)
Ответ: zyxw
1.3 Миша заполнял таблицу истинности функции F=(x∨y)∧¬(y≡z)∧¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w,x,y,z.
| F | ||||
| 1 | 1 | 1 | ||
| 0 | 1 | 0 | 1 | |
| 1 | 1 | 0 | 1 |
Определите, какому столбцу таблицы соответствует каждая из переменных w,x,y,z.
Решение:
...
Ответ: zyxw
1.4 Логическая функция F задаётся выражением ((z→x)∧(x→w))∨(y≡(z∨x)). На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки.
| ? | ? | ? | ? | F |
| 1 | 0 | |||
| 1 | 1 | 0 | ||
| 1 | 1 | 0 |
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x,y,z,w.
Решение:
...
Ответ: yxwz
1.5 Логическая функция F задаётся выражением y∧(x∨z)∨¬(y∨z)∨w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности соответствует каждая из переменных w,x,y,z.
| ? | ? | ? | ? | F |
| 1 | 0 | 1 | 0 | |
| 1 | 0 | 0 | ||
| 0 | 0 | 1 | 0 |
Решение:
...
Ответ: xywz
1.6 Миша заполнял таблицу истинности логической функции F=w→((x→z)→y), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w,x,y,z
| ? | ? | ? | ? | F |
| 0 | 1 | 0 | ||
| 0 | 1 | 0 | ||
| 0 | 0 |
Решение:
...
Ответ: wyxz
Задания второй линейки уровня ЕГЭ
Задача №1 Миша заполнял таблицу истинности функции F=((x→y)∨(z≡x))∧(w→z), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w,x,y,z.
| ? | ? | ? | ? | F |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x,y,z,w. В ответе напишите буквы w,x,y,z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Ответ: zwxy
Задача №2 После заполнения трех таблиц истинности для трех логических функций, взяли ровно по одной строке из каждой таблицы.
| Логическая функция F | ? | ? | ? | ? | F |
| (w→y)≡(x∧z) | 1 | 0 | 1 | 0 | 1 |
| ¬x∨¬y∨¬z∨w | 0 | 1 | 1 | 1 | 0 |
| (z∨w)∧y∧x | 1 | 1 | 1 | 0 | 1 |
Определите, какому столбцу таблицы соответствует каждая из переменных w,x,y,z. В ответе запишите буквы w,x,y,z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Ответ: wyxz
Задача №3 Логическая функция F задаётся выражением: (z≡¬x)→((w→¬y)∧(y→x)) Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных w,x,y,z.
| ? | ? | ? | ? | F |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | ||
| 0 | 0 |
Ответ: yzxw
Задача №4 Логическая функция F задаётся выражением (p3→p1)→(p4∨¬p2). На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какой столбец в таблице каждой переменной в выражении.
| ? | ? | ? | ? | F |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 1 | 0 | |
| 1 | 1 | 0 |
В ответе напишите буквы x,y,z,w в том порядке, который соответствует переменным p1,p2,p3 и p4 в выражении. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Функция задана выражением ¬p2∨p1, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
| x | y | ¬x∨y |
| 0 | 1 | 0 |
В этом случае p1 соответствует переменная y, а p2 – переменная x. В ответе следует написать yx.
Ответ: ywxz
