Задание 2

Рассмотрим несколько примеров

Пример 1

Задание

Логическая функция $F$ задаётся выражением

F=\lnot x \lor y\lor(\lnot z \land w)

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

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

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

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

Java
C++
Python

public class Example1 {
    // список перебираемых значений переменной boolean
    static boolean[] booleanValues = new boolean[]{false, true};

    // логическая функция, аргументы которой мы подбираем
    static boolean f(boolean x, boolean y, boolean z) {
        return impl(x, y) && impl(y, z);
    }

    // операция импликации(следования)
    static boolean impl(boolean a, boolean b) {
        return !a || b;
    }

    // главный метод программы
    public static void main(String[] args) {
        // выводим заголовок
        System.out.println("x y z");
        // перебираем все наборы значений
        for (boolean xV0 : booleanValues)
            for (boolean yV0 : booleanValues)
                for (boolean zV0 : booleanValues)
                        // если функция даёт ложь
                        if (!f(xV0, yV0, zV0))
                            // выводим этот набор аргументов
                            System.out.println(
                                    (xV0 ? 1 : 0) + " " + (yV0 ? 1 : 0) + " " + (zV0 ? 1 : 0)
                            );

    }
}

#include <iostream>

// список перебираемых значений переменной boolean
int booleanValues[] = {0, 1};

// операция импликации(следования)
bool impl(int a, int b) {
    return !a || b;
}

// логическая функция, аргументы которой мы подбираем
bool f(int x, int y, int z) {
    return impl(x, y) && impl(y, z);
}


// главный метод программы
int main() {
    // выводим заголовок
    std::cout << "x y z" << std::endl;
    // перебираем все наборы значений
    for (int xV0: booleanValues)
        for (int yV0: booleanValues)
            for (int zV0: booleanValues)
                // если функция даёт ложь
                if (!f(xV0, yV0, zV0))
                    std::cout << xV0 << " " << yV0 << " " << zV0 << std::endl;
    return 0;
}

# операция импликации(следования)
def impl(a, b):
    return not a or b


# логическая функция, аргументы которой мы подбираем
def f(x, y, z):
    return impl(x, y) and impl(y, z)


# выводим заголовок
print("x y z")
# перебираем все наборы значений
for xV0 in [0, 1]:
    for yV0 in [0, 1]:
        for zV0 in [0, 1]:
            # если функция даёт ложь
            if not f(xV0, yV0, zV0):
                # выводим этот набор аргументов
                print(str(xV0) + " " + str(yV0) + " " + str(zV0))

На выходе получим

В Java для перевода boolean в цифры 0 и 1 я использовал тернарное выражение условие?результат_если_да:результат_если нет. Его можно заменить обычным условием if. Для перебора я создал массив из двух элементов и для каждой переменной написал свой вложенный цикл, который перебирает значения из этого массива.

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

Например, у $y$ всегда значения "Ложь", а в исходной таблице столбец с тремя нулями только один и он - первый. Поэтому на первом месте точно стоит $y$ .

Подбирая такие столбцы, получим ответ: $y$ , $z$ , $w$ , $x$ .

Если значения функции различны, то так просто задачу не получится решить. Однако для начала попробуйте просто вывести все наборы, но добавьте в вывод ещё и значение функции $F$ :

Java
C++
Python

        ...
        // перебираем все наборы значений
        for (boolean xV0 : booleanValues)
            for (boolean yV0 : booleanValues)
                for (boolean zV0 : booleanValues)
                    // выводим этот набор аргументов
                    System.out.println(
                        (xV0 ? 1 : 0) + " " + (yV0 ? 1 : 0) + " " + (zV0 ? 1 : 0) + " " + (f(xV0, yV0, zV0) ? 1 : 0))
                    );
        ...

    ...
    // перебираем все наборы значений
    for (int xV0: booleanValues)
        for (int yV0: booleanValues)
            for (int zV0: booleanValues)
                // если функция даёт ложь
                if (!)
                    std::cout << xV0 << " " << yV0 << " " << zV0 << " " << f(xV0, yV0, zV0) << std::endl;
    ...

# выводим заголовок
print("x y z")
# перебираем все наборы значений
for xV0 in [0, 1]:
    for yV0 in [0, 1]:
        for zV0 in [0, 1]:
            # выводим этот набор аргументов и значение функции
            print(str(xV0) + " " + str(yV0) + " " + str(zV0) + " " + str(f(xV0, yV0, zV0))

И попробуйте найти соответствие.

Пример 2

Если же вручную подобрать значения сходу не получается, проще написать переборщик соответствий. Для этого нужны будут перестановки. Подробнее о них написано в Задании 1.

Решим такую задачу:

Задание

Логическая функция $F$ задаётся выражением

F=(x\lor y)\land\lnot(y\equiv z)\land\lnot w

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

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

Java
C++
Python

import java.util.Arrays;

public class Example2 {
    // имена колонок
    static char[] names = {'x', 'y', 'z', 'w'};
    // список перебираемых значений переменной boolean
    static boolean[] booleanValues = new boolean[]{false, true};

    // логическая функция, аргументы которой мы подбираем
    static boolean f(boolean x, boolean y, boolean z, boolean w) {
        return (x || y) && (y != z) && !w;
    }

    // проверка значений в линии на совпадение
    static int findLine(boolean xV, boolean yV, boolean zV, boolean wV, boolean f, boolean[][] combinations) {
        if (xV && zV && f && combinations[0] == null) {
            return 0;
        }
        // обязательно надо сначала проверить эту строку, потому что она
        if (!xV && yV && !wV && f && combinations[1] == null) {
            return 1;
        }
        if (yV && zV && !wV && f && combinations[2] == null) {
            return 2;
        }
        return -1;
    }

    // обработка перестановки
    static void processPermutation(int[] p) {
        // найденные комбинации, их три, потому что известных строчек таблицы истинности 3
        boolean[][] combinations = new boolean[16][];
        // кол-во найденных комбинаций
        int foundCombinationCnt = 0;
        // перебираем все варианты значений для каждой логической переменной
        // из таблицы истинности, значений всего два: true и false
        for (boolean xV0 : booleanValues)
            for (boolean yV0 : booleanValues)
                for (boolean zV0 : booleanValues)
                    for (boolean wV0 : booleanValues) {
                        // чтобы использовать перестановку, построим на основе четырёх логических
                        // переменных массив
                        boolean[] values = new boolean[]{
                                xV0, yV0, zV0, wV0
                        };

                        // получим значения логических переменных с учётом перестановки
                        // т.е. мы по сути формируем строку значений, которую потом будем сверять с данной
                        boolean xV = values[p[0]];
                        boolean yV = values[p[1]];
                        boolean zV = values[p[2]];
                        boolean wV = values[p[3]];
                        // ищем подходящую строку таблицы
                        int lineNum = findLine(xV, yV, zV, wV, f(xV0, yV0, zV0, wV0), combinations);
                        // если строка найдена и ещё не сохранена соответствующая этой строке комбинация
                        if (lineNum != -1) {
                            // сохраняем комбинацию
                            combinations[lineNum] = values;
                            foundCombinationCnt++;
                        }
                    }
        // если найдено три комбинации
        if (foundCombinationCnt == 3) {
            System.out.println("++++++++++++++++++++++++++++++");
            System.out.println("перестановка: " + Arrays.toString(p));
            // выводим шапку
            for (int i = 0; i < 4; i++) {
                System.out.print(names[p[i]] + " ");
            }
            System.out.println();
            // выводим сохранённые комбинации
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 4; j++) {
                    System.out.print((combinations[i][p[j]] ? 1 : 0) + " ");
                }
                System.out.println();
            }
        }
    }


    // функция-генератор перестановок
    static void permute(int[] p, int pos) {
        // Если мы дошли до последнего элемента
        if (pos == p.length - 1) {
            processPermutation(p);
        } else { // иначе
            // Перебираем все оставшиеся элементы
            for (int i = pos; i < p.length; i++) {
                // меняем местами текущий элемент и перебираемый
                swap(p, pos, i);
                // Вызываем Рекурсию для следующего элемента
                permute(p, pos + 1);
                // меняем местами обратно
                swap(p, pos, i);
            }
        }
    }

    // главный метод программы
    public static void main(String[] args) {
        // создаём массив индексов
        int[] arr = new int[]{0, 1, 2, 3};
        // запускаем перебор перестановок
        permute(arr, 0);
    }

    // поменять местами элементы массива arr с индексами l и r
    public static void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }

}

#include <iostream>
#include <vector>
#include <algorithm>

// имена колонок
char names[] = {'x', 'y', 'z', 'w'};
// список перебираемых значений переменной boolean
int booleanValues[]{0, 1};

// логическая функция, аргументы которой мы подбираем
int f(int x, int y, int z, int w) {
    return (x || y) && (y != z) && !w;
}

// проверка значений в линии на совпадение
int findLine(int xV, int yV, int zV, int wV, int f, std::vector<std::vector<int>> combinations) {
    //std::cout << combinations << std::endl;
    if (xV && zV && f && combinations[0].empty()) {
        return 0;
    }
    // обязательно надо сначала проверить эту строку, потому что она
    if (!xV && yV && !wV && f && combinations[1].empty()) {
        return 1;
    }
    if (yV && zV && !wV && f && combinations[2].empty()) {
        return 2;
    }
    return -1;
}

// обработка перестановки
static void processPermutation(std::vector<int> p) {
    // список найденных операций, в данной задаче их три, поэтому и в вектор  добавляем 3 вектора 
    std::vector<std::vector<int>> combinations;
    combinations.reserve(3);
    for (int i = 0; i < 3; i++)
        combinations.emplace_back();

    // кол-во найденных комбинаций
    int foundCombinationCnt = 0;
    // перебираем все варианты значений для каждой логической переменной
    // из таблицы истинности, значений всего два: true и false
    for (int xV0: booleanValues)
        for (int yV0: booleanValues)
            for (int zV0: booleanValues)
                for (int wV0: booleanValues) {
                    // чтобы использовать перестановку, построим на основе четырёх логических
                    // переменных массив
                    int values[] = {xV0, yV0, zV0, wV0};

                    // получим значения логических переменных с учётом перестановки
                    // т.е. мы по сути формируем строку значений, которую потом будем сверять с данной
                    int xV = values[p[0]];
                    int yV = values[p[1]];
                    int zV = values[p[2]];
                    int wV = values[p[3]];
                    // ищем подходящую строку таблицы
                    int lineNum = findLine(xV, yV, zV, wV, f(xV0, yV0, zV0, wV0), combinations);
                    // если строка найдена и ещё не сохранена соответствующая этой строке комбинация
                    if (lineNum != -1) {
                        // сохраняем комбинацию
                        combinations[lineNum].assign(values, values + 4);
                        foundCombinationCnt++;
                    }
                }
    // если найдено три комбинации
    if (foundCombinationCnt == 3) {
        std::cout << "++++++++++++++++++++++++++++++" << std::endl;
        std::cout << "permutation: ";
        for (int i = 0; i < 4; i++)
            std::cout << p[i] << " ";
        std::cout << std::endl;
        // выводим шапку
        for (int i = 0; i < 4; i++) {
            std::cout << names[p[i]] << " ";
        }
        std::cout << std::endl;
        // выводим сохранённые комбинации
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 4; j++) {
                std::cout << combinations[i][p[j]] << " ";
            }
            std::cout << std::endl;
        }
    }
}


// главный метод программы
int main() {
    // для перестановок вектор должен быть отсортированным
    std::vector<int> origin = {0, 1, 2, 3};
    do {
        processPermutation(origin);
    } while (std::next_permutation(origin.begin(), origin.end()));
    return 0;
}

import itertools

# имена колонок
names = ['x', 'y', 'z', 'w']


# операция импликации(следования)
def impl(a, b):
    return not a or b


# логическая функция, аргументы которой мы подбираем
def f(x, y, z, w):
    return (x or y) and (y != z) and not w


# проверка значений в линии на совпадение
def find_line(xV, yV, zV, wV, f, combinations):
    if xV and zV and f and combinations[0] is None:
        return 0
    # обязательно надо сначала проверить эту строку, потому что она
    if not xV and yV and not wV and f and combinations[1] is None:
        return 1
    if yV and zV and not wV and f and combinations[2] is None:
        return 2

    return -1


# обработка перестановки
def process_permutation(p):
    # найденные комбинации
    combinations = [None] * 16
    # кол-во найденных комбинаций
    foundCombinationCnt = 0
    # перебираем все варианты значений для каждой логической переменной
    # из таблицы истинности, значений всего два: true и false
    for xV0 in [0, 1]:
        for yV0 in [0, 1]:
            for zV0 in [0, 1]:
                for wV0 in [0, 1]:
                    # чтобы использовать перестановку, построим на основе четырёх логических
                    # переменных массив
                    values = [xV0, yV0, zV0, wV0]

                    # получим значения логических переменных с учётом перестановки
                    # т.е. мы по сути формируем строку значений, которую потом будем сверять с данной
                    xV = values[p[0]]
                    yV = values[p[1]]
                    zV = values[p[2]]
                    wV = values[p[3]]
                    # ищем подходящую строку таблицы
                    lineNum = find_line(xV, yV, zV, wV, f(xV0, yV0, zV0, wV0), combinations);
                    # если строка найдена и ещё не сохранена соответствующая этой строке комбинация
                    if lineNum != -1:
                        # сохраняем комбинацию
                        combinations[lineNum] = values
                        foundCombinationCnt = foundCombinationCnt + 1

    # если найдено три комбинации
    if foundCombinationCnt == 3:
        print("++++++++++++++++++++++++++++++")
        print(p)
        # выводим шапку
        s = ""
        for i in range(4):
            s += names[p[i]] + " "
        print(s)

        # выводим сохранённые комбинации
        for i in range(3):
            s = ""
            for j in range(4):
                s += str(combinations[i][p[j]]) + " "

            print(s)


# получаем все перестановки
permutations = list(itertools.permutations([0, 1, 2, 3]))
# перебираем перестановки
for permutation in permutations:
    process_permutation(permutation)

Получим:

++++++++++++++++++++++++++++++
перестановка: [2, 1, 0, 3]
z y x w 
1 0 1 0 
0 1 0 0 
0 1 1 0 

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

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

Сама проверка возвращает, какой линии соответствует этот набор. Если он не удовлетворяет ни одной, возвращается -1. Если набор найден, сохраняем его в соответствующий элемент массива, хранящего все комбинации

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

По сути, обработчик перестановки теперь универсален, при четырёх переменных вам нужно менять только методы findLine() и f().

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

Если у вас в задаче другое кол-во переменных, то в генерации перестановок нужно указать массив из стольких индексов, сколько используется у вас, также необходимо изменить размер списка комбинаций до $2^n$ , где $n$ - кол-во логических переменных.

Также не забудьте поменять массив заголовков names.

Пример 3

Задание

Логическая функция F задаётся выражением

F=((x\land y)\lor(w\Rightarrow z))\equiv(z\equiv x))

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

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

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

Я привёл только методы, у которых реализация отличается от реализации в предыдущем задании

Отдельно написана функция impl() для вычисления импликации

Java
C++
Python

    // логическая функция, аргументы которой мы подбираем
    static boolean f(boolean x, boolean y, boolean z, boolean w) {
        return ((x && !y) || impl(w, z)) == (z == x);
    }

    // операция импликации(следования)
    static boolean impl(boolean a, boolean b) {
        return !a || b;
    }

    // проверка значений в линии на совпадение
    static int findLine(boolean xV, boolean yV, boolean zV, boolean wV, boolean f, boolean[][] combinations) {
        if (!yV && !zV && wV && f && combinations[0] == null) {
            return 0;
        }
        if (!xV && yV && !zV && !wV && f && combinations[1] == null) {
            return 1;
        }
        if (!xV && wV && f && combinations[2] == null) {
            return 2;
        }
        return -1;
    }

// логическая функция, аргументы которой мы подбираем
int f(int x, int y, int z, int w) {
    return ((x && !y) || impl(w, z)) == (z == x);
}

// проверка значений в линии на совпадение
int findLine(int xV, int yV, int zV, int wV, int f, std::vector<std::vector<int>> combinations) {
    if (!yV && !zV && wV&& f && combinations[0].empty()) {
        return 0;
    }
    // обязательно надо сначала проверить эту строку, потому что она
    if (!xV && yV && !zV && !wV  && f && combinations[1].empty()) {
        return 1;
    }
    if (!xV && wV && f && combinations[2].empty()) {
        return 2;
    }
    return -1;
}

# логическая функция, аргументы которой мы подбираем
def f(x, y, z, w):
    return ((x and not y) or impl(w, z)) == (z == x)


# проверка значений в линии на совпадение
def find_line(xV, yV, zV, wV, f, combinations):
    if not yV and not zV and wV and f and combinations[0] is None:
        return 0
    # обязательно надо сначала проверить эту строку, потому что она
    if not xV and yV and not zV and not wV and f and combinations[1] is None:
        return 1
    if not xV and wV and f and combinations[2] is None:
        return 2

    return -1

Получим:

++++++++++++++++++++++++++++++
перестановка: [2, 1, 3, 0]
z y w x 
1 0 0 1 
0 1 0 0 
0 1 1 1 

Пример 4

Задание

F=((x\land y)\lor(y\land z))\equiv(x\Rightarrow w)\land(w\Rightarrow z))

Логическая функция F задаётся выражением

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

Java
C++
Python

    // логическая функция, аргументы которой мы подбираем
    static boolean f(boolean x, boolean y, boolean z, boolean w) {
        return ((x && y) || (y && z)) == (impl(x, w) && impl(w, z));
    }

    // проверка значений в линии на совпадение
    static int findLine(boolean xV, boolean yV, boolean zV, boolean wV, boolean f, boolean[][] combinations) {
        if (!xV && yV && zV && wV && f && combinations[0] == null) {
            return 0;
        }
        if (!xV && yV && !zV && f && combinations[1] == null) {
            return 1;
        }
        if (!xV && yV && !zV && f && combinations[2] == null) {
            return 2;
        }
        return -1;
    }

// логическая функция, аргументы которой мы подбираем
int f(int x, int y, int z, int w) {
    return ((x && y) || (y && z)) == (impl(x, w) && impl(w, z));
}

// проверка значений в линии на совпадение
int findLine(int xV, int yV, int zV, int wV, int f, std::vector<std::vector<int>> combinations) {
    //std::cout << combinations << std::endl;
    if (!xV && yV && zV && wV && f && combinations[0].empty()) {
        return 0;
    }
    // обязательно надо сначала проверить эту строку, потому что она
    if (!xV && yV && !zV && f && combinations[1].empty()) {
        return 1;
    }
    if (!xV && yV && !zV && f && combinations[2].empty()) {
        return 2;
    }
    return -1;
}

# логическая функция, аргументы которой мы подбираем
def f(x, y, z, w):
    return ((x and y) or (y and z)) == (impl(x, w) and impl(w, z))


# проверка значений в линии на совпадение
def find_line(xV, yV, zV, wV, f, combinations):
    if not xV and yV and zV and wV and f and combinations[0] is None:
        return 0
    # обязательно надо сначала проверить эту строку, потому что она
    if not xV and yV and not zV and f and combinations[1] is None:
        return 1
    if not xV and yV and not zV and f and combinations[2] is None:
        return 2

    return -1

Получим:

++++++++++++++++++++++++++++++
перестановка: [0, 3, 2, 1]
x w z y 
0 1 1 1 
0 1 0 0 
0 1 0 1 

Пример 5

Задание

Логическая функция F задаётся выражением

F=((w\lor y)\equiv x)\lor((w\Rightarrow z)\land(y\Rightarrow w))

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

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

Java
C++
Python

    // логическая функция, аргументы которой мы подбираем
    static boolean f(boolean x, boolean y, boolean z, boolean w) {
        return (((w || y) == x)) || (impl(w, z) && impl(y, w));
    }

    // операция импликации(следования)
    static boolean impl(boolean a, boolean b) {
        return !a || b;
    }

    // проверка значений в линии на совпадение
    static int findLine(boolean xV, boolean yV, boolean zV, boolean wV, boolean f, boolean[][] combinations) {
        // сначала проверяем вторую строку, т.к. она - частный случай первой
        if (xV && wV && !f && combinations[0] == null) {
            return 0;
        }
        if (wV && !f && combinations[1] == null) {
            return 1;
        }
        if (xV && zV && !f && combinations[2] == null) {
            return 2;
        }
        return -1;
    }

// логическая функция, аргументы которой мы подбираем
int f(int x, int y, int z, int w) {
    return (((w || y) == x)) || (impl(w, z) && impl(y, w));
}

// проверка значений в линии на совпадение
int findLine(int xV, int yV, int zV, int wV, int f, std::vector<std::vector<int>> combinations) {
    //std::cout << combinations << std::endl;
    if (xV && wV && !f && combinations[0].empty()) {
        return 0;
    }
    // обязательно надо сначала проверить эту строку, потому что она
    if (wV && !f && combinations[1].empty()) {
        return 1;
    }
    if (xV && zV && !f && combinations[2].empty()) {
        return 2;
    }
    return -1;
}

# логическая функция, аргументы которой мы подбираем
def f(x, y, z, w):
    return (((w or y) == x)) or (impl(w, z) and impl(y, w))


# проверка значений в линии на совпадение
def find_line(xV, yV, zV, wV, f, combinations):
    # сначала проверяем вторую строку, т.к. она - частный случай первой
    if xV and wV and not f and combinations[0] is None:
        return 0

    if wV and not f and combinations[1] is None:
        return 1

    if xV and zV and not f and combinations[2] is None:
        return 2

    return -1

Получим:

++++++++++++++++++++++++++++++
перестановка: [1, 0, 2, 3]
y x z w 
1 0 0 1 
0 0 0 1 
1 0 1 0 

Пример 6

Иногда задание на алгебру логики проще подобрать вручную, чем вообще составлять программу. Правда, для самоконтроля я всё равно советую, если останется свободное время, всё же написать программу.

Рассмотрим задачу:

Задание

Каждое логическое выражение $A$ и $B$ зависит от одного и того же набора из 5 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы. Каково минимально возможное число единиц в столбце значений таблицы истинности выражения $A \lor\lnot B$ ?

Решение:

полная таблица истинности каждого выражения с пятью переменными содержит 25 = 32 строки

в каждой таблице по 4 единицы и по 28 (= 32 – 4) нуля

выражение $A \lor\lnot B$ равно нулю тогда и только тогда, когда $A = 0$ и $B = 1$

минимальное количество единиц в таблице истинности выражения $A \lor\lnot B$ будет тогда, когда там будет наибольшее число нулей, то есть в наибольшем количество строк одновременно $A = 0$ и $B = 1$

по условию $A = 0$ в 28 строках, и $B = 1$ в 4 строках, поэтому выражение $A \lor\lnot B$ может быть равно нулю не более чем в 4 строках, оставшиеся $32 – 4 = 28$ могут быть равны 1

Ответ: 28.

Пример 7

Задание

Дан фрагмент таблицы истинности для выражения $F$ :

x1	x2	x3	x4	x5	F
0	0	1	0	0	1
1	0	1	0	1	1
0	1	1	1	0	1

Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение $x_1$ не совпадает с $F$

полная таблица истинности выражения с пятью переменными содержит 25 = 32 строки

в приведённой части таблицы в двух строках значение $x_1$ совпадает с $F$ , а в одной – не совпадает

во всех оставшихся (неизвестных) $32 – 3 = 29$ строках значения $x_1$ и $F$ могут не совпадать

всего несовпадающих строк может быть $1 + 29 = 30$ .

Ответ: 30

Пример 8

Задание

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

x1	x2	x3	x4	x5	x6	x7	x8	F
	0						1	0
1			0					1
			1				1	1

Каким выражением может быть F?

$x_1 \land \lnot x_2 \land x_3 \land \lnot x_4 \land x_5 \land x_6 \land\lnot x_7 \land\lnot x_8$
$x_1 \lor x_2 \lor x_3 \lor \lnot x_4 \lor\lnot x_5 \lor\lnot x_6 \lor\lnot x_7 \lor\lnot x_8$
$\lnot x_1 \land x_2 \land \lnot x_3 \land x_4 \land x_5 \land \lnot x_6 \land\lnot x_7 \land\lnot x_8$
$x_1 \lor \lnot x_2 \lor x_3 \lor \lnot x_4 \lor\lnot x_5 \lor\lnot x_6 \lor\lnot x_7 \lor\lnot x_8$

Решение

В последнем столбце таблицы истинности видим две единицы, откуда сразу следует, что это не может быть цепочка операций «И» (конъюнкций), которая даёт только одну единицу; поэтому ответы 1 и 3 заведомо неверные

Анализируем первую строку таблицы истинности; мы знаем в ней только два значения - $x_2=0$ и $x_8=1$ .

Чтобы в результате в первой строке получить 0, необходимо, чтобы переменная $x_8$ входила в сумму с инверсией (тогда из 1 получится 0!), это условие выполняется для обоих оставшихся вариантов, 2 и 4

кроме того, переменная $x_2$ должна входить в выражение без инверсии (иначе соответствующее слагаемое в первой строке равно 1, и это даст в результате 1); этому условию не удовлетворяет выражение 4; остается один возможный вариант – выражение 2

Ответ: 2

Задания для самостоятельного выполнения

Пример 1​

Пример 2​

Пример 3​

Пример 4​

Пример 5​

Пример 6​

Пример 7​

Пример 8​

Пример 1

Пример 2

Пример 3

Пример 4

Пример 5

Пример 6

Пример 7

Пример 8