Задача 2 ЕГЭ по информатике - полное решение на Питоне

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне 

 

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

Первый этап (построение таблицы истинности) часто выполняется с помощью программы. Написать программу для этой цели - задача очень несложная. Но мы рассмотрим возможность решить задачу полностью чисто программным путём. (Честно говоря, не берусь настойчиво рекомендовать данный способ. Но если у вас с программированием всё отлично - то почему бы и нет? И в любом случае - это достаточно красивая задача).

Алгоритм решения по сути прост. Составим полную таблицу истинности для приведённой в условии задачи формулы. Затем будем переставлять столбцы переменных в полученной таблицу всеми возможными способами и отбирать из таблицы с переставленными столбцами несколько строк (по числу строу в таблице в условии). Если полученная нами таблица совпадает с таблицей в условии - то нужная перестановка найдена. 

Для примера рассмотрим следующую задачу. Дана логическая функция

(x ≡ ¬y) → ((z → ¬w) ∧ (w → y))

и частично заполненная таблица истинности

?	?	?	?	F
1	1	0	1	1
0		0		0
			0	0

Я намеренно выбрал пример, где логическая функция принимает значения то 0, то 1.

Напишем на питоне функцию, которая получает кортеж v из значений переменных x, y, z, w и выдает строку таблицы истинности для данных значений переменных.

def sti(v): # строка таблицы истинности
    x,y,z,w=v # распаковка переменных
    f=(x==y) or ((not z or not w) and (not w or y)) # значение функции
    return ''.join(map(str,v))+str(int(f)) # строка переменных + значение

(Я заменяю импликацию a→ b на выражение not a or b. Часто пишут a<=b, но такой способ мне не очень нравится.)

Нам также пригодится функция, которая переставляет первые символы строки в указанном порядке. Первый её параметр - это строка, а второй - кортеж, содержащий целые числа от 0 до числа параметров и задающий перестановку.

def perm(s,p):
    return ''.join(s[i] for i in p) + s[len(p):]

Проверим работу функции, выполнив строку

print(perm('abcdef',(3,2,1,0)))  # результат: dcbaef

Теперь можно писать программу. Импортируем модули itertools и fnmatch.

import itertools,fnmatch

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

matrix=(
'11011',
'0?0?0',
'???00')

Зададим число параметров функции и количество строк в таблице в условии.

numlines=len(matrix) # число строк в таблице из условия
numvars=4 # число переменных

Получим полную таблицу истинности для нашей функции.

table=[sti(v) for v in itertools.product((0,1), repeat=numvars)] # таблица истинности

Теперь начинается настоящая работа.

Будем генерировать все возможные перестановки чисел 0, 1, 2, 3 с помощью функции permutations. Для каждой перестановки соответственно переставим значения переменных в таблице истинности и получим таблицу permtable. Из этой таблицы будем выбирать по три строки во всех вщзможных комбинациях (опять-таки с помощью функции permutations) и сравнивать результат с таблицей из условия. Если одно совпадёт с другим - то мы нашли нужную перестановку. Переставляем символы в строке xyzw по тому же закону, по которому мы переставляли значения переменных, и печатаем ответ.

Для сопоставления нашего фрагмента таблицы с таблицей из условия используется функция fnmatch из одноименного модуля. Первым параметром в ней указана строка, полученная объединением строк из нашей таблицы, а вторым - строка-объединение строк из таблицы условия. Функция fnmatch отождествляет знак вопроса во втором параметре с любым символом на соответствующем месте в первом параметре. (Именно поэтому мы использовали знак вопроса при задании таблицы из условия.) Эта функция хорошо знакома всем, кто решал задачу 25 в её современном варианте.

Вот полный текст программы:

 

def sti(v): # строка таблицы истинности
    x,y,z,w=v # распаковка переменных
    f=(x==y) or ((not z or not w) and (not w or y)) # значение функции
    return ''.join(map(str,v))+str(int(f)) # строка переменных + значение
    
def perm(s,p): # перестановка первых символов строки
    return ''.join(s[i] for i in p) + s[len(p):]

import itertools,fnmatch
matrix=( # таблица из условия
'11011',
'0?0?0',
'???00')
numlines=len(matrix) # число строк в таблице из условия
numvars=4 # число переменных
table=[sti(v) for v in itertools.product((0,1), repeat=numvars)] # таблица истинности
for p in itertools.permutations(range(numvars)): # перестановки переменных
    permtable=[perm(line,p) for line in table] # таблица с переставленными переменными
    for mytable in itertools.permutations(permtable,numlines): # Выбор строк
        if fnmatch.fnmatch(''.join(mytable),''.join(matrix)): # Сопоставление
            print(perm('xyzw',p)) # Перестановка названий переменных и печать

Печатается верный ответ ywzx.

Программа легко адаптируется для случая, когда заданы две функции: F1 и F2. Всё, что надо изменить - это функцию sti и таблицу matrix.

Для примера рассмотрим задачу с двумя функциями

F1  =  (x ∨¬ y) → (w ≡ z)
F2  =  (x ∨¬ y) ≡ (w → z)

и таблицей

?	?	?	?	F1	F2
0		0	0	0	0
	1	1		0
	0	0	0		0

 

Всё, что нужно изменить в программе - это переписать функцию sti и, разумеется, изменить таблицу с исходными данными matrix.

def sti(v):
    x,y,z,w=v
    f1=not (x or not y) or (w==z)
    f2=(x or not y) == (not w or z)
    return ''.join(map(str,v))+str(int(f1))+str(int(f2))

matrix=(
'0?0000',
'?11?0?',
'?000?0')

Печатается верный ответ ywxz - причём два раза. Что это значит?

Если ответ печатается несколько раз, то есть несколько способов сопоставить строки таблицы истинности строкам в условии. (Кстати, это автоматом решает задачи с вопросами типа "Сколькими способами можно поставить в соответствие переменные w, x, y, z столбцам таблицы истинности функции F?")

(c) Ю.Д.Красильников, 2024 г.