Задание на алгебру логики егэ информатика

Задача 1

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
bool f(int A, int B, int C, int D, int E, int F){
    return (!(!A || F) && B && !C && (!D || E));
}
int main() {
    int count = 0;
    for (int A = 0; A <= 1; ++A)
        for (int B = 0; B <= 1; ++B)
            for (int C = 0; C <= 1; ++C)
                for (int D = 0; D <= 1; ++D)
                    for (int E = 0; E <= 1; ++E)
                        for (int F = 0; F <= 1; ++F)
                            if (f(A, B, C, D, E, F) == false)
                                count++;
    cout << count;
    return 0;
}

Задача 2

Задача 3

Задача 4

bool f(int x, int y, int z, int w){
    return (((x && z) || !x) && !w && y);
}
int main() {
    cout << "x y z w F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                for (int w = 0; w <= 1; ++w)
                    if (f(x, y, z, w) == true)
                        cout << x << " " << y << " "
                            << z << " " << w << " " << f(x, y, z, w) << endl;
    return 0;
}

Задача 5

bool f(int x, int y, int z, int w){
    return ((!y || w) || (!x && z));
}
int main() {
    cout << "x y z w F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                for (int w = 0; w <= 1; ++w)
                    if (f(x, y, z, w) == false)
                        cout << x << " " << y << " "
                            << z << " " << w << " " << f(x, y, z, w) << endl;
    return 0;
}

Задача 6

Задача 7

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
bool f(int x, int y, int z){
    return ((x || y) && (!z || y));
}
int main() {
    cout << "x y z F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                    if (f(x, y, z) == false)
                        cout << x << " " << y << " "
                            << z << " " << f(x, y, z) << endl;
    return 0;
}

Задача 8

Задача 9

Задача 10

Задача 11

Задача 12

Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.

Основоположником алгебры логики является английский математик и логик Дж. Буль (1815–1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.

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

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

Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.

Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».

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

В алгебре логики различаются простые (элементарные) высказывания, обозначаемые латинскими буквами (A, B, C, D, …), и сложные (составные), составленные из нескольких простых с помощью логических связок, например таких, как «не», «и», «или», «тогда и только тогда», «если … то». Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний.

Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».

Тогда составное высказывание «Алгебра логики успешно применяется в теории электрических цепей и при синтезе релейно-контактных схем» можно кратко записать как А и В; здесь «и» — логическая связка. Очевидно, что поскольку элементарные высказывания А и В истинны, то истинно и составное высказывание А и В.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.

Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.

Основные операции алгебры логики

1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А), которое называется отрицанием исходного высказывания, обозначается символически чертой сверху ($A↖{-}$) или такими условными обозначениями, как ¬, ‘not’, и читается: «не А», «А ложно», «неверно, что А», «отрицание А». Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖{-}$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B ) истинно.

Операция, используемая относительно одной величины, называется унарной. Таблица значений данной операции имеет вид

или

Высказывание $A↖{-}$ ложно, когда А истинно, и истинно, когда А ложно.

Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖{-}$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.

2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В»), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В, а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.

Таблица истинности операции имеет вид

или

Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.

Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.

3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В»), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В». Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B. Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

Таблица истинности операции имеет вид

или

Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.

Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.

4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В) и читается: «либо А, либо В». Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.

Таблица истинности операции имеет вид

или

Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.

5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если…, то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.

Таблица истинности операции имеет вид

или

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

6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В, которое читается: «А эквивалентно B». Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно». Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».

Таблица истинности операции эквивалентности имеет вид

или

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

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

Приоритет выполнения логических операций следующий: отрицание («не») имеет самый высокий приоритет, затем выполняется конъюнкция («и»), после конъюнкции — дизъюнкция («или»).

С помощью логических переменных и логических операций любое логическое высказывание можно формализовать, т. е. заменить логической формулой. При этом элементарные высказывания, образующие составное высказывание, могут быть абсолютно не связаны по смыслу, но это не мешает определять истинность или ложность составного высказывания. Например, высказывание «Если пять больше двух (А), то вторник всегда наступает после понедельника (В)» — импликация А → В, и результат операции в данном случае — «истина». В логических операциях смысл высказываний не учитывается, рассматривается только их истинность или ложность.

Рассмотрим, например, построение составного высказывания из высказываний А и В, которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.

Примеры решения задач

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X < 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Решение. Последовательность выполнения операций следующая: сначала выполняются операции сравнения в скобках, затем дизъюнкция, и последней выполняется операция импликации. Операция дизъюнкции ∨ ложна тогда и только тогда, когда оба операнда ложны. Таблица истинности для импликации имеет вид

Отсюда получаем:

1) для X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) для X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) для X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 2) → (X > 5)) .

Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.

Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.

Решение. Рассмотрим последовательно все предложенные слова:

1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;

4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;

5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.

Построение таблиц истинности логических выражений

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

Удобной формой записи при нахождении значений функции является таблица, содержащая, кроме значений переменных и значений функции, также значения промежуточных вычислений. Рассмотрим пример построения таблицы истинности для формулы ${X1}↖{-} ∧ X2 ∨ {X1 ∨ X2}↖{-} ∨ X1$.

Если функция принимает значение 1 при всех наборах значений переменных, она является тождественно-истинной; если при всех наборах входных значений функция принимает значение 0, она является тождественно-ложной; если набор выходных значений содержит как 0, так и 1, функция называется выполнимой. Приведенный выше пример является примером тождественно-истинной функции.

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

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

Алгоритм построения ДНФ следующий:

1. в таблице истинности функции выбирают наборы аргументов, для которых логические формы равны 1 («истина»);
2. все выбранные логические наборы как логические произведения аргументов записывают, последовательно соединив их между собой операцией логической суммы (дизъюнкции);
3. для аргументов, которые являются ложными, в построенной записи проставляют операцию отрицания.

Пример. Построить функцию, определяющую, что первое число равно второму, используя метод ДНФ. Таблица истинности функции имеет вид

Решение. Выбираем наборы значений аргументов, в которых функция равна 1. Это первая и четвертая строки таблицы (строку заголовка при нумерации не учитываем).

Записываем логические произведения аргументов этих наборов, объединив их логической суммой: X1 ∧ X2 ∨ X1 ∧ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих ложное значение (четвертая строка таблицы; второй набор в формуле; первый и второй элементы): X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Ответ: F(X1, X2) = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

2. Конъюнктивно нормальная форма (КНФ) — произведение сумм, образованных из переменных и их отрицаний для истинных значений.

Алгоритм построения КНФ следующий:

1. в таблице истинности выбирают наборы аргументов, для которых логические формы равны 0 («ложь»);
2. все выбранные логические наборы как логические суммы аргументов записывают последовательно, соединив их между собой операцией логического произведения (конъюнкции);
3. для аргументов, которые являются истинными, в построенной записи проставляют операцию отрицания.

Примеры решения задач

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

Решение. Выбираем наборы значений аргументов, в которых функция равна 0. Это вторая и третья строки (строку заголовка при нумерации не учитываем).

Записываем логические суммы аргументов этих наборов, объединив их логическим произведением: X1 ∨ X2 ∧ X1 ∨ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих истинное значение (вторая строка таблицы, первый набор формулы, второй элемент; для третьей строки, а это второй набор формулы, первый элемент): X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Таким образом, получена запись логической функции в КНФ.

Ответ: X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Полученные двумя методами значения функций являются эквивалентными. Для доказательства этого утверждения используем правила логики: F(X1, X2) = X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2 = X1 ∧ ${X1}↖{-}$ ∨ X1 ∧ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ ${X2}↖{-}$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ 0 = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Пример 2. Построить логическую функцию для заданной таблицы истинности:

Решение. Используем алгоритм ДНФ для построения исходной функции:

Искомая формула: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 .

Ее можно упростить: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 = X2 ∧ (X1 ∨ ${X1}↖{-}$) = X2 ∧ 1 = X2.

Пример 3. Для приведенной таблицы истинности построить логическую функцию, используя метод ДНФ.

Искомая формула: X1 ∧ X2 ∧ X ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∪ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$.

Формула достаточно громоздка, и ее следует упростить:

X1 ∧ X2 ∧ X3 ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∨ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$ = X2 ∧ X3 ∧ (X1 ∨ ${X1}↖{-}$) ∨ X1 ∧ ${X3}↖{-}$ ∧ (X2 ∨ ${X2}↖{-}$) = X2 ∧ X3 ∨ X1 ∧ ${X3}↖{-}$.

Таблицы истинности для решения логических задач

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

Примеры решения задач

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

Решение. Очевидно, что результатом решения будет таблица, в которой искомая функция Y(X1, X2, X3) будет иметь значение «истина», если какие-либо две переменные имеют значение «истина».

Пример 2. Составить расписание уроков на день, учитывая, что урок информатики может быть только первым или вторым, урок математики — первым или третьим, а физики — вторым или третьим. Возможно ли составить расписание, удовлетворив всем требованиям? Сколько существует вариантов расписания?

Решение. Задача легко решается, если составить соответствующую таблицу:

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

1. математика, информатика, физика;
2. информатика, физика, математика.

Пример 3. В спортивный лагерь приехали трое друзей — Петр, Борис и Алексей. Каждый из них увлекается двумя видами спорта. Известно, что таких видов спорта шесть: футбол, хоккей, лыжи, плавание, теннис, бадминтон. Также известно, что:

1. Борис — самый старший;
2. играющий в футбол младше играющего в хоккей;
3. играющие в футбол и хоккей и Петр живут в одном доме;
4. когда между лыжником и теннисистом возникает ссора, Борис мирит их;
5. Петр не умеет играть ни в теннис, ни в бадминтон.

Какими видами спорта увлекается каждый из мальчиков?

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

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

Из условия 4 следует, что Борис не увлекается ни лыжами, ни теннисом, а из условий 3 и 5, что Петр не умеет играть в футбол, хоккей, теннис и бадминтон. Следовательно, любимые виды спорта Петра — лыжи и плавание. Занесем это в таблицу, а оставшиеся клетки столбцов «Лыжи» и «Плавание» заполним нулями.

Из таблицы видно, что в теннис может играть только Алексей.

Из условий 1 и 2 следует, что Борис не футболист. Таким образом, в футбол играет Алексей. Продолжим заполнять таблицу. Внесем в пустые ячейки строки «Алексей» нули.

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

Ответ: Петр увлекается лыжами и плаванием, Борис играет в хоккей и бадминтон, а Алексей занимается футболом и теннисом.

Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 2022. Сегодня разоблачим второе задание!

Кто незнаком с основными логическими операциями, можете посмотреть прошлогоднюю статью по заданию 2 из ЕГЭ по информатике.

В этой статье будут раскрыты методики решения 2 задания через язык программирования Питон.

Будем перебирать для каждой логической переменной все возможные варианты в программе. А логическая переменная всего два значения может принимать: 1 или 0 (истину или ложь). Таким образом, если к примеру у нас 4 переменные, мы получим 2⁴=16 различных комбинаций.

Кто знаком с мощнейшим методом для 2 задания из ЕГЭ по информатике, о котором я рассказывал в прошлогодней статье, тот поймёт, что мы будем применять тот же самый мощнейший метод, но автоматизированный с помощью питона.

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

Перейдём к практике решения задач задания 2 с помощью языка программирования Python.

Задача (Классическая)

Миша заполнял таблицу истинности логической функции F

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

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

Определите, какому столбцу таблицы соответствует каждая из переменных
w, x, y, z.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут
соответствующие им столбцы (сначала буква, соответствующая первому
столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.

Пример. Функция F задана выражением ¬x / y, зависящим от двух
переменных, а фрагмент таблицы имеет следующий вид.

В этом случае первому столбцу соответствует переменная y, а второму
столбцу – переменная x. В ответе следует написать: yx.

Решение:

Решать задачу будем с помощью шаблона на языке Python (Питон).

print('x y z w')
for x in range(0, 2):
    for y in range(0, 2):
        for w in range(0, 2):
            for z in range(0, 2):
                if (not(w) or z) and ((not(y) or x) == (not(z) or y)):
                    print(x, y, z, w)

В задаче у нас 4 переменные, значит, формируем 4 вложенных цикла. В каждом цикле перебираем все возможные значения для конкретной переменной. Мы перебираем значения 0 и 1.

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

Четыре вложенных цикла проверяют все возможные варианты (2⁴ = 16 вариантов), и мы получим таблицу истинности, почти такую же, как нам и дали в условии задачи.

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

Запустим программу, и на экране распечатается табличка:

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

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

Сразу видно, что первый столбец принадлежит переменной x, только там могут быть все единицы.

Второй столбец принадлежит переменной w, только там могут быть все нули.

У нас остались две пустые клеточки в самой таблице. Нам нужно где-то поставить единицу, а где-то ноль, потому что у нас остались столбцы с двумя единицами и одним нулём, а так же с двумя нулями и одной единицей. Если мы в третий столбец поставим единицу, а в четвёртый ноль, то первая строчка и вторая будут совпадать.

А в условии сказано, что строки не должны повторяться. Поэтому нужно ноль и единицу расставить наоборот.

Получается, что в третий столбец идёт z, а в четвёртый y

Ответ: xwzy

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

Задача (Классическая, закрепление)

Миша заполнял таблицу истинности функции (x ≡ ¬y) → ((x ∧ w) ≡ z), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных
w, x, y, z.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут
соответствующие им столбцы (сначала буква, соответствующая первому
столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.

Пример. Функция F задана выражением ¬x / y, зависящим от двух
переменных, а фрагмент таблицы имеет следующий вид.

В этом случае первому столбцу соответствует переменная y, а второму
столбцу – переменная x. В ответе следует написать: yx.

Решение:

Воспользуемся программой на языке Python.

print('x y z w')
for x in range(0, 2):
    for y in range(0, 2):
        for w in range(0, 2):
            for z in range(0, 2):
                if not( not(( x == (not(y)) )) or ((x and w) == z) ):
                    print(x, y, z, w)

От прошлой программы эта программа отличается только функцией!

В таблице видим, что функция должна выдавать ноль. Поэтому в условии мы функцию «оборачиваем» в not().

После == операцию not() мы заключили в скобки, чтобы не было синтаксической ошибки.

Получаем следующую таблицу истинности:

Разгадаем, где какая переменная находится.

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

Получается, что второй столбец достаётся переменной z.

В первом столбце должно быть две единицы. На эту роль подходит переменная y.

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

А в последний столбец идёт переменная w по остаточному принципу.

Ответ: yzxw

А как Питон справится с более сложной функцией из примерного варианта ЕГЭ по информатике?

Задача (Сложная функция)
Логическая функция F задаётся выражением ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Источник задачи сайт решу ЕГЭ: https://inf-ege.sdamgia.ru/

Решение:

Запрограммируем функцию на языке Python.

print('x y z w')
for x in range(0, 2):
    for y in range(0, 2):
        for w in range(0, 2):
            for z in range(0, 2):
                if not( ((not(x) or y) and (not(y) or w)) or (z == (x or y)) ):
                    print(x, y, z, w)

Запустим программу и расставим переменные по своим местам.

Переменная z может быть только в третьем столбце.

Во второй столбец идёт переменная w, только этот столбец может иметь одну единицу.

Посмотрим на строчку, где у w стоит единица. В этой же строчке и у x единица. Значит, x идёт в последний столбец, а y в первый столбец.

Ответ: ywzx

Тот же шаблон работает, когда у нас во втором задании три переменные.

Задача (Три переменные)

(№ 1608) Логическая функция F задаётся выражением (¬x ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z)

На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

Источник задачи сайт К. Ю. Полякова: https://kpolyakov.spb.ru/

Решение:

Для трёх переменных шаблон на Питоне отлично работает.

print('x y z')
for x in range(0, 2):
    for y in range(0, 2):
        for z in range(0, 2):
               if (not(x) and z) or (not(x) and not(y) and not(z)):
                    print(x, y, z)

Здесь и так понятно, куда какая переменная идёт.

Ответ: yxz

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

Задача (Разные значения функции)

Логическая функция F задаётся выражением (¬a ∨ b ∨ ¬c) ∧ (b ∨ ¬c). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

В ответе напишите буквы a, b, c в том порядке, в котором идут соответствующие им столбцы (без разделителей).

Источник задачи сайт К. Ю. Полякова: https://kpolyakov.spb.ru/

Решение:

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

print('a b c')
for a in range(0, 2):
    for b in range(0, 2):
        for c in range(0, 2):
               if (not(a) or b or not(c)) and (b or not(c)):
                    print(a, b, c)

В таблице 6 строчек, в которых главная функция превращается в единицу. Далее эти строчки и будем рассматривать. У нас тоже получилось 6 строчек.

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

Переменная b имеет четыре единицы, значит, она расположена в первом столбце.

Переменной c достаётся последний столбец.

Ответ: bac

Ещё одна интересная задача для подготовки к ЕГЭ по информатике 2022.

Задача(С подвохом)

Логическая функция F задаётся выражением a ≡ b ∨ b → c.

На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

Источник задачи группа Евгения Джобса: https://vk.com/inform_web

Решение:

Подвох заключается в том, что если мы переведём бездумно функцию на язык Питон, то получится a==b or not(b) or c. Но у нас существуют приоритеты для логических операций, которые описаны в прошлогодней статье по подготовке к ЕГЭ по информатике.

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

Операцию b ∨ b можно представить, как просто b. Ведь, если b принимает значение 0, тогда будет 0 ∨ 0 = 0. Если значение будет 1, то 1 ∨ 1 = 1. Поэтому формулу можно переписать следующим образом:

a ≡ b → c

a == (not(b) or c)

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

Дальше решаем как обычно.

print('a b c')
for a in range(0, 2):
    for b in range(0, 2):
        for c in range(0, 2):
               if a == (not(b) or c):
                    print(a, b, c)

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

Последний столбец занимает переменная a, т.к. только в последний столбец может влезть две единицы.

В строчке, где у a ноль, так же ноль и у переменной c. Значит, во второй столбец идёт переменная c. Если мы ноль поставим в первой строчке в первом столбце, то получится первый столбец из всех нулей. А такого у нас в таблице истинности нет.

Тогда переменная b в первом столбце.

Ответ: bca

В настоящее время на вступительных экзаменах
по информатике есть много заданий по теме
“алгебра логики”. Цель данного урока –
закрепление навыков решения заданий ЕГЭ по
информатике с использованием элементов алгебры
логики.

Цели урока:

• Формирование умения применять полученные
  знания на практике;
• Развитие умения построения таблиц истинности
  по заданным формулам;
• Развитие умения решать текстовые задачи с
  использованием законов логики.

Задачи урока:

• Воспитательная – развитие
  познавательного интереса, логического мышления.
• Образовательная – повторение основ
  математической логики, выполнение практических
  заданий.
• Развивающая –  развитие логического
  мышления, внимательности.

Ход урока

1. Повторение логических операций и законов.
2. Применение логических операций и законов на
   практике.
3. Объяснение домашнего задания.

Сегодня мы с вами завершаем тему “Основы
логики” и применим основные логические
операции, законы преобразования для решения
заданий ЕГЭ по информатике.

Урок идет параллельно с презентацией. <Приложение1>

1. Повторение логических операций и
законов.

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

Вопросы:

1. Основоположник формальной логики?

Аристотель.

2. Основоположник алгебры логики?

Джордж Буль.

3. Перечислите логические операции:

¬ отрицание (инверсия)
&, / конъюнкция (“И”)
V дизъюнкция (“ИЛИ”)

логическое следование (импликация)
равнозначность
(эквивалентность)

4. В чем смысл закона двойного отрицания?

Двойное отрицание исключает отрицание.

5. Законы де Моргана (законы общей инверсии).

Отрицание дизъюнкции является конъюнкцией
отрицаний:

¬(A V B) = ¬A / ¬B

Отрицание конъюнкции является дизъюнкцией
отрицаний:

¬(A /B) = ¬A V ¬B

6. Закон идемпотентности (одинаковости).

A V A = A

A / A = A

7. В чём смысл закона исключения третьего?

Из двух противоречащих высказываний об одном и
том же одно всегда истинно, второе ложно,
третьего не дано:

A V ¬А= 1

8. О чём закон противоречия?

Не могут быть одновременно истинны утверждение
и его отрицание:

A / ¬А= 0

9. Закон исключения констант.

Для логического сложения:

A V 1 = 1 A V 0 = A

Для логического умножения:

A / 1 = A A / 0 = 0

10. Как выразить импликацию через дизъюнкцию?

А В = ¬A V В

Пример 1. (Задание А11 демоверсии 2004 г.)

Для какого имени истинно высказывание:

¬ (Первая буква имени гласная -> Четвертая
буква имени согласная)?

1) ЕЛЕНА

2) ВАДИМ

3) АНТОН

4) ФЕДОР

Решение. Сложное высказывание состоит из
двух простых высказываний:

А – первая буква имени гласная,

В – четвертая буква имени согласная.

¬ (А В) = ¬ (¬A V
В) = (¬ (¬А) / ¬B) = A / ¬B

Применяемые формулы:

1. Импликация через дизъюнкцию А ? В = ¬A V В

2. Закон де Моргана ¬(A V B) = ¬A / ¬B

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

(Первая буква имени гласная / Четвертая буква
имени гласная)

Ответ: 3

Пример 2. (Задание А12 демоверсии 2004 г.)

Какое логическое выражение равносильно
выражению ¬ (А / ¬B)?

1) A / B

2) A / B

3) ¬A / ¬B

4) ¬A / B

Решение. ¬ (А / ¬B)= ¬ А / ¬ (¬B)= ¬ А / B

Ответ: 4

Пример 3.

Составить таблицу истинности для формулы

¬ (B / C) V (A/C B)

Порядок выполнения логических операций:

¬ (B / C) V (A/C B)

2   1   5   3   4

Составить таблицу истинности.

Сколько строк будет в вашей таблице? 3
переменных: А, В, С; 2³=8

Сколько столбцов? 5 операций + 3 переменных = 8

Решение:

A	B	C	(B / C)	¬ (B / C)	A/C	(A/C ? B)	¬ (B / C) V (A/C B)
0	0	0	0	1	0	1	1
0	0	1	0	1	0	1	1
0	1	0	0	1	0	1	1
0	1	1	1	0	0	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	1	1	1
1	1	0	0	1	0	0	1
1	1	1	1	0	1	1	1

Какие ответы получились в последнем столбце?

Ответ: 1

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

Решим этот пример аналитическим методом:

упрощаем выражение

¬ (B / C) V (A/C B)=
(применим формулу для импликации)

¬ (B / C) V ¬ (A / C) V B = (применим 1 и 2 законы де
Моргана)

(¬B V ¬C) V (¬A V ¬C) V B = (уберём скобки)

¬B V ¬C V ¬A V ¬C V B= (применим переместительный
закон)

¬B V B V ¬C V ¬C V ¬A = (закон исключения третьего,
закон идемпотентности)

1 V ¬С V ¬A = 1 V ¬A = 1 (закон исключения констант)

Ответ: 1, означает, что формула является
тождественно-истинной или тавтологией.

Логическое выражение называется тождественно-ложным,
если оно принимает значения 0 на всех наборах
входящих в него простых высказываний.

(задание 3 домашнего задания)

Пример 4.

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

Для обозначения логической операции “ИЛИ” в
запросе используется символ I, а для логической
операции “И” – символ &.

А	Законы & Физика
Б	Законы I (Физика & Биология)
В	Законы & Физика & Биология & Химия
Г	Законы I Физика I Биология

Решение:

Первый способ основан на рассуждении.
Рассуждая логически, мы видим, что больше всего
будет найдено страниц по запросу Г, так как при
его исполнении будут найдены и страницы со
словом “законы”, и страницы, со словом
“физика”, и страницы со словом “биология”.
Меньше всего будет найдено страниц по запросу В,
так как в нем присутствие всех четырех слов на
искомой странице. Осталось сравнить запросы А и
Б. По запросу Б будут найдены все страницы,
соответствующие запросу А, (так как в последних
обязательно присутствует слово “законы”), а
также страницы, содержащие одновременно слова
“физика” и “биология”. Следовательно по
запросу Б будет найдено больше страниц, чем по
запросу А. Итак, упорядочив запросы по
возрастанию страниц, получаем ВАБГ.

Ответ: ВАБГ.

Второй способ предполагает использование
графического представления операций над
множествами. (Смотри презентацию)

Пример 5. (Задание А16 демоверсии 2006 г.)

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

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

“Пол=’м’ ИЛИ Химия>Биология”?

1) 5

2) 2

3) 3

4) 4

Решение:

Выбираем записи: Мальчики (двое) и
Химия>Биология (трое, но один мальчик, уже
взялся 1 раз). В итоге 4 записи удовлетворяют
условию.

Задание 6. (Задание В4 демоверсии 2007 г)

В школьном первенстве по настольному теннису в
четверку лучших вошли девушки: Наташа, Маша, Люда
и Рита. Самые горячие болельщики высказали свои
предположения о распределении мест в дальнейших
состязаниях.

Один считает, что первой будет Наташа, а Маша
будет второй.

Другой болельщик на второе место прочит Люду, а
Рита, по его мнению, займет четвертое место.

Третий любитель тенниса с ними не согласился.
Он считает, что Рита займет третье место, а Наташа
будет второй.

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

Какое место на чемпионате заняли Наташа, Маша,
Люда, Рита?

(В ответе перечислите подряд без пробелов
числа, соответствующие местам девочек в
указанном порядке имен.)

Решение:

Обозначим высказывания:

Н1 = “первой будет Наташа”;

М2 = “второй будет Маша”;

Л2 = “второй будет Люда”;

Р4 = “четвертой будет Рита”;

Р3 = “третьей будет Рита”;

Н2 = “второй будет Наташа”.

Согласно условию:

из высказываний 1 болельщика следует, что Н1VМ2
истинно;

из высказываний2 болельщика следует, что Л2VР4
истинно;

из высказываний 3 болельщика следует, что Р3VН2
истинно.

Следовательно, истинна и конъюнкция

(Н1VМ2) / (Л2VР4) / (Р3VН2) = 1.

Раскрыв скобки получим:

(Н1VМ2) / (Л2VР4) / (Р3VН2) = (Н1/Л2V Н1/Р4 V М2/Л2 V М2/Р4) /
(Р3VН2)=

Н1/ Л2/Р3 V Н1/Р4/Р3 V М2/Л2/Р3 V М2/Р4/Р3 V Н1/Л2/Н2 V
Н1/Р4/Н2 V М2/Л2/Н2 V М2/Р4/Н2 = Н1/ Л2/Р3 V 0 V 0 V 0 V 0 V 0
V 0 V= Н1/ Л2/Р3

Наташа-1, Люда-2, Рита-3, а Маша-4.

Задание 1. (Задание В8 демоверсии 2007г)

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

Для обозначения логической операции “ИЛИ” в
запросе используется символ |, а для логической
операции “И” – &.

А	волейбол | баскетбол | подача
Б	волейбол | баскетбол | подача | блок
В	волейбол | баскетбол
Г	волейбол & баскетбол & подача

Задание 2 (Задание В4 демоверсии 2008г)

Перед началом Турнира Четырех болельщики
высказали следующие предположения по поводу
своих кумиров:

A) Макс победит, Билл – второй;

B) Билл – третий. Ник – первый;

C) Макс – последний, а первый – Джон.

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

Какое место на турнире заняли Джон, Ник, Билл,
Макс?

(В ответе перечислите подряд без пробелов места
участников в указанном порядке имен.)

Оценки за урок.

Типовое задание № 2

(базовый уровень,
время – 3 мин)

Что проверяется:

Умение строить таблицы
истинности и логические схемы.

1.5.1.
Высказывания, логические операции, кванторы, истинность высказывания

1.1.6.
Умение строить модели объектов, систем и процессов в виде таблицы истинности
для логического высказывания

Про обозначения

К
сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной»
математической логике (Ù,Ú,¬), неудобны, интуитивно
непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему
стыду, до сих пор иногда путает Ù и Ú.
Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком
умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+»
(логическое сложение). В разных учебниках используют разные обозначения. К
счастью, в начале задания ЕГЭ приводится расшифровка закорючек (Ù,Ú,¬), что еще раз подчеркивает проблему.

Что нужно знать:

условные
обозначения логических операций

¬ A,                   не
A (отрицание, инверсия)

A Ù B,            A и B (логическое
умножение, конъюнкция)

A Ú B,                   A или B
(логическое сложение, дизъюнкция)

A → B                  импликация (следование)

A º B         
         эквивалентность (равносильность)

операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A → B = ¬ A Ú B или в других обозначениях A → B =

иногда для упрощения выражений полезны формулы де Моргана:

¬ (A Ù
B) = ¬ A Ú ¬ B             

¬ (A Ú
B) = ¬ A Ù ¬ B             

если в выражении нет скобок, сначала выполняются все операции
«НЕ», затем – «И», затем – «ИЛИ», «импликация», и самая последняя –
«эквивалентность»

таблица
истинности выражения определяет его значения при всех возможных комбинациях
исходных данных

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

количество
разных логических функций, удовлетворяющих неполной таблице истинности, равно , где  – число отсутствующих строк; например, полная
таблица истинности выражения с тремя переменными содержит 23=8 строчек, если
заданы только 6 из них, то можно найти 28-6=22=4 разных логических функции,
удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)

логическая
сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все
слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение
истинно)

логическое
произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда,
когда все сомножители одновременно равны единице, а в остальных случаях равно 0
(выражение ложно)

логическое
следование (импликация) А→В равна 0 тогда и только тогда, когда A (посылка)
истинна, а B (следствие) ложно

эквивалентность
АºB равна 1 тогда и только тогда,
когда оба значения одновременно равны 0 или одновременно равны 1

По материалам К.Ю. Полякова с сайта ЕГЭ по информатике: подготовка к
ЕГЭ-2022 по информатике, разбор задач ЕГЭ-2022 по информатике, материалы для
подготовки к ЕГЭ (kpolyakov.spb.ru)

Решение задач
второго типа в MS Excel

Алгоритм решения

1.
Составить таблицу входных значения, перечисляя все комбинации переменных в
порядке возрастания двоичного кода. Для этого подсчитать n число переменных в
исходном выражении, выписать наборы входных переменных.  Количество
наборов входных переменных 2ⁿ.

2. Для каждой строки находим логическое решение. Для этого:

·       
Подсчитать
общее число логических операций в выражении;

·       
Установить последовательность
выполнения логических операций с учетом скобок и приоритетов.

3. Выполнить поиск значения функции,
отсортировать данное значение по искомой части (1 или 0).

4. Сопоставить исходную таблицу и вновь
полученную.

Используемые фукции в MS Excel

Примеры:

1 (Задача 158 с сайта К.Ю.
Полякова). Логическая
функция F задаётся выражением   ¬x Ù y Ù (w ® z). На рисунке приведён фрагмент
таблицы истинности функции F, содержащий все наборы аргументов, при
которых функция F истинна. Определите, какому столбцу таблицы истинности
функции F соответствует каждая из переменных x, y, z,
w.

В ответе напишите буквы x, y,
z, w в том порядке, в котором идут соответствующие им столбцы.

Решение

1.
 Подсчитаем количество переменных: x, y, z, w – 4 переменных, следовательно,
ищем количество наборов по формуле: 2ⁿ
= 2⁴ = 16 наборов. Заполняем разными возможными вариантами (см.
рисунок)

2.
Определим наборы операций:

         1) ¬x

         2) (w ®
z)

         3) ¬x Ù y Ù
(w ® z)

Ищем
результаты действий.

Результат вычислений   Введенные
формулы

Следующий
шаг это отфильтровать значения 1 по столбцу H:

Сопоставим
с условием:

Анализируем:

0
– всегда X          1 – всегда Y          011 – Z                 001
— W

Ответ:
YXZW

2(Задача 168 с сайта К.Ю.
Полякова). Логическая
функция F задаётся выражением 
x Ú (¬y
Ú z Ú ¬w) Ù (y Ú ¬z). На рисунке приведён фрагмент
таблицы истинности функции F, содержащий все наборы аргументов, при
которых функция F ложна. Определите, какому столбцу таблицы истинности
функции F соответствует каждая из переменных x, y, z,
w.

В
ответе напишите буквы x, y, z, w в том порядке, в
котором идут соответствующие им столбцы.

Ответ:
WXZY

3(Задача 178 с сайта К.Ю.
Полякова). Логическая
функция F задаётся выражением (Øz ÚØ
y) ® (x º z). На рисунке приведён частично
заполненный фрагмент таблицы истинности функции F, содержащий
неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F
соответствует каждая из переменных x, y, z.

В
ответе напишите буквы x, y, z в том порядке, в котором
идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких
разделителей между буквами ставить не нужно.

Ответ:
YXZ

4 (Задача 188 с сайта К.Ю.
Полякова).
Логическая функция F задаётся выражением (w Ù y) Ú ((x ® w) º (y ® z)). На рисунке приведён частично
заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся
строки. Определите, какому столбцу таблицы истинности функции F соответствует
каждая из переменных x, y, z, w.

В
ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие
им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами
ставить не нужно.

Ответ:
ZWYX

5 (Задача 198 с сайта К.Ю.
Полякова).
Логическая функция F задаётся выражением
(w ® y) Ù ((x ® z) º (y ® x)). На рисунке приведён частично заполненный фрагмент таблицы
истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу
таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

В
ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие
им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами
ставить не нужно.

Ответ:
WZXY