Чьи это части?

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

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

Для примера рассмотрим функцию от двух аргументов – F(X1, X2). Область определения функции содержит четыре элемента:

Определить конкретную функцию F(X1, X2) можно, указав какое значение - 0 или 1, она принимает в каждой из четырех точек области определения. Например, функцию F1(X1, X2) можно определить следующим образом:

F1(0, 0) = 0; F1(0, 1) = 0; F1(1, 0) = 0; F1(1, 1) = 1;

Функцию F2(X1, X2) определим так:

F1(0, 0) = 0; F1(0, 1) = 1; F1(1, 0) = 1; F1(1, 1) = 1;

Надеюсь, Вы узнали эти функции, - они хорошо Вам знакомы. Первая из них – это конъюнкция, называемая также функцией "И", или логическим умножением. Вторая функция – это дизъюнкция или логическое сложение.

F1(X1, X2) = X1 X2; F2(X1, X2) = X1 | X2;

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

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

Итак, логическую функцию можно задать формулой или таблицей истинности.

Теперь можно сформулировать задачу, которую нам предстоит решать.

Задача Дан фрагмент таблицы истинности, определяющий некоторую функцию F. Даны логические функции F1, F2, …Fk, заданные формулами. Определить, какая из функций Fj совпадает с функцией F на заданном фрагменте таблицы истинности.

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

Например, если заданы две функции F1 и F2 – дизъюнкция и конъюнкция, а фрагмент, задающий F, состоит из одного набора, то для набора {01} можно однозначно сказать, что F совпадает с конъюнкцией, если значение F равно 0, и совпадает с дизъюнкцией, если значение равно 1. Для набора {00} F совпадает с обеими функциями, если значение F равно 0, и не совпадает ни с одной из двух функций, если значение равно 1.

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

Рассмотрим теперь конкретную задачу, соответствующую образцу.

Задача. Дан фрагмент таблицы истинности, определяющий некоторую функцию F(x1, x2, x3, x4):

Даны логические функции F1, F4, F7, F10, заданные формулами:

Определить, какая из функций Fj совпадает с функцией F на заданном фрагменте таблицы истинности.

Общий прием решения подобных задач прост. Необходимо построить фрагмент таблицы истинности для заданных наборов и заданных функций. Затем сравнить полученные результаты с заданным фрагментом функции F, после чего принять решение, анализируя результаты сравнения. Для построения таблицы истинности для функции, заданной формулой, необходимо знать определения базовых функций и уметь проводить вычисления по формуле с учетом приоритета операций. Напомню, вначале необходимо вычислить выражения в скобках, затем выполнять операции в порядке – Отрицание, И, Или, Импликация, Эквивалентность.

Построим такую таблицу:

Как видно, на данном фрагменте с функцией F совпадает только одна функция F1.

Конечно, не всегда требуется строить полную таблицу. В нашем случае, если начать вычисления с третьего набора, то сразу видно, что функция F10 имеет значение, отличное от значения функции F на этом наборе, поэтому дальше не имеет смысла вычислять значение F10 на других наборах. Вычислив значения оставшихся трех функций на первом наборе, отфильтруем функцию F7. Функция F4 будет отфильтрована на втором наборе. Наконец, вычислив значение оставшейся функции F1 на последнем четвертом наборе нашего фрагмента, обнаружим совпадение F и F1 на данном фрагменте.