Логика высказываний и булевы функции

Доказать, что количество $k$-мерных граней в $n$-мерном кубе равно $F(n, k)=C_{n}^{k} \cdot 2^{n-k}$. Найти общее количество $F(n)$ граней $n$-мерного куба.

Пусть $\bar{a}=\left(a_{1}, a_{2}, \ldots , a_{n}\right)$ и $\bar{b}=\left(b_{1}, b_{2}, \ldots , b_{n}\right)$ — два набора (две точки) $n$-мерного единичного куба $\mathbb {B}^{n}$. Расстоянием Хэмминга между $\bar{a}$ и $\bar{b}$ называется число $H(\bar{a}, \bar{b})=\sum_{i=1}^{n}\left|a_{i}-b_{i}\right|$. Доказать, что это расстояние удовлетворяет следующим свойствам:

Пусть $\bar{a}, \bar{b} \in \mathbb {B}^{n}$ — точки $n$-мерного единичного куба, $H(\bar{a}, \bar{b})=k$. Доказать, что тогда

Пусть в последовательности векторов

каждый следующий элемент получен из предыдущего заменой одного из нулей на единицу. Доказать, что система уравнений $H\left(\bar{x}, \bar{a}^{(i)}\right)=k_{i}$, $i=0, \ldots , n, k_{i} \in \omega$, имеет не более одного решения в $\mathbb {B}^{n}$.

Найти вершины единичного куба $\mathbb {B}^{5}$, которые отстоят от вершин $(0,0,0,0,0),(1,0,0,0,0),(1,1,0,0,0),(1,1,1,0,0),(1,1,1,1,0)$, $(1,1,1,1,1)$ на указанные расстояния соответственно:

Какие подмножества вершин $\mathbb {B}^{4}$ соответствуют следующим булевым функциям:

Построить таблицы значений для следующих булевых функций:

Назовём триггером булеву функцию $T$ с несколькими аргументами, для которой выполнено $T(q, 0, \ldots , 0)=q$ для любого $q \in \mathbb {B}$. Выписать всевозможные

Для каждой из следующих формул определить её глубину и построить таблицу задаваемой ею функции:

Определить, какие из следующих формул логики высказываний являются тождественно истинными:

В представленной на рис. 115 таблице показано кодирование десятичных цифр от 0 до 9 с помощью четырёх пропозициональных переменных $A, B, C, D \in \mathbb {B}$. Не перечисленные в таблице варианты значений $A, B, C$ и $D$ являются ошибочными кодами. Какие из следующих булевых формул задают множество всех ошибочных кодов:

Используя таблицу кодов из предыдущей задачи и предполагая, что код не является ошибочным, построить формулу с четырьмя переменными $A, B, C$ и $D$, которая будет иметь значение 1 тогда и только тогда, когда кодируемое число

Переменные $(A_{1}, B_{1}, C_{1}, D_{1})$ и $(A_{2}, B_{2}, C_{2}, D_{2})$ кодируют числа $x_{1}$ и $x_{2}$ соответственно (см. задачу 115). Предполагая, что оба кода не являются ошибочными, записать формулу, которая будет иметь значение 1 тогда и только тогда, когда

Переменные $(C_{1}, D_{1})$ и $(C_{2}, D_{2})$ кодируют числа $x_{1}$ и $x_{2}$ соответственно из множества $\left\{ 0,1,2,3\right\}$ (см. задачу 115). Записать формулы $p_{A}, p_{B}, p_{C}$ и $p_{D}$, значения которых кодируют произведение этих чисел.

Какие из следующих условий можно выразить булевыми формулами от переменных $x_{1}, x_{2}, x_{3}, x_{4}$, использующими лишь логические связки $\wedge$ и $\vee$?

Назовём наборы $\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n}$ и $\beta =\left(\beta_{1}, \ldots , \beta_{n}\right) \in \mathbb {B}^{n}$ соседними, если они находятся в соседних строках таблицы для функции от $n$ переменных, то есть представляют двоичные записи чисел $i_{\alpha }$ и $i_{\beta }$, для которых $\left|i_{\alpha }-i_{\beta }\right|=1$.

Найти количество функций в $\mathcal{P}_{n}$, которые на каждой паре соседних наборов принимают

Найти количество $n$-местных булевых функций, принимающих значение 1 ровно на $k$ наборах.

Найти количество функций в $\mathcal{P}_{n}$, которые меняют своё значение при изменении любого аргумента.

Найти количество функций в $\mathcal{P}_{n}$, коммутативных по любой паре аргументов, то есть значение которых не меняется при перестановке произвольных аргументов.

Назовём наборы $\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n}$ и $\beta =\left(\beta_{1}, \ldots , \beta_{n}\right) \in \mathbb {B}^{n}$ противоположными, если $\alpha_{i}+\beta_{i}=1$ для всякого $i$ (иначе говоря, $\alpha_{i}=1$ в том и только том случае, когда $\beta_{i}=0$).

Найти количество функций в $\mathcal{P}_{n}$, которые на каждой паре противоположных наборов принимают разные значения.

Пусть $n=2 k$. Назовём набор $\alpha =\left(\alpha_{1}, \ldots , \alpha_{n}\right) \in \mathbb {B}^{n}$ парным, если $\alpha_{i}=\alpha_{k+i}$ для всех $i=1, \ldots , k$, то есть $\alpha =\alpha^{\prime } \alpha^{\prime }$ для некоторого набора $\alpha^{\prime }$ размера $k$. Найти количество функций в $\mathcal{P}_{n}$, которые на всех парных наборах принимают одинаковое значение.

Определить, сколько всего трёхместных булевых функций можно построить, используя не более одной связки из таблиц 1 и 2 на стр. 36 и при том не более одного раза.

Пусть $F$ — конечное множество булевых функций, $\varepsilon$ — положительная, сколь угодно малая константа. Доказать, что при достаточно больши́х $n$ формулами над $F$ с количеством символов менее $2^{n} / n$ можно представить не более $2^{2^{n}} / n^{1-\varepsilon }$ булевых функций. Таким образом, почти все булевы функции представляются только «длинными» формулами.

Аргумент $x_{i}$ булевой функции $f$ называется фиктивным, если значение $f$ никогда не меняется при изменении значения $x_{i}$. Найти количество $n$-местных булевых функций, не имеющих фиктивных аргументов, для $n=2,3,4$.

Индукцией по построению формулы $\Phi$ доказать неравенство

Привести пример, когда неравенство будет строгим.

Администратор базы данных обнаружил, что одна или несколько из трёх записей его базы $A, B$ и $C$ ошибочна. Он установил, что

Программист Пётр использовал в своей программе на языке С три целочисленные переменные $x, y, z$. В определённом месте программы он поместил условный оператор: if $(\mathrm{x} * \mathrm{y}>=0| | \mathrm{x} * \mathrm{z}>=0)$ $\mathrm{x}=1$; else $\mathrm{x}=2$; Проанализировав свою программу, Пётр установил, что перед выполнением этого оператора выполнены следующие условия:

Комитет состоит из пяти членов. Решения принимаются большинством голосов, однако, если председатель голосует «против», то решение не принимается. Построить формулу логики высказываний, зависящую от пяти пропозициональных переменных $x_{1}, x_{2}, x_{3}, x_{4}, y$ ($x_{i}$ означает, что $i$-й член комитета голосует «за», $y$ означает, что председатель голосует «за»), значение которой равно 1 тогда и только тогда, когда в результате голосования решение принимается.

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

Детектив Ш. Холмс подозревает в совершении преступления трёх лиц: $A, B$ и $C$. Он установил, что

Детектив Э. Пуаро подозревает в совершении преступления трёх лиц: $A, B$ и $C$. Они дали следующие показания: - $A$ : если $B$ преступник, то $C$ невиновен; - $B$ : если $A$ виновен, то и $C$ является преступником; - $C: A$ преступник. Э. Пуаро установил, что (а) если $A$ сказал правду, то $B$ соврал, и (б) показания $C$ ложны. Описать знания Э. Пуаро в виде формулы логики высказываний и построить таблицу её значений. Может ли он сделать вывод, что $B$ является преступником? Мог ли преступник быть один?

Пусть во всех зоопарках, где есть львы и носороги, нет жирафов; во всех зоопарках, где есть носороги и нет жирафов, есть львы; наконец, во всех зоопарках, где есть львы и жирафы, есть и носороги. Как вы думаете, может ли существовать такой зоопарк, в котором есть львы, но нет ни жирафов, ни носорогов?

Анна, Беатриса и Вера как-то обнаружили, что все они в одинаковых джинсах. Известно, что у Анны есть джинсы с карманами, узкие джинсы и вылинявшие джинсы без карманов; у Беатрисы джинсы без карманов и вылинявшие узкие джинсы с карманами. И наконец, Вера имеет джинсы-клёши и синие узкие джинсы с карманами. Как выглядят их одинаковые джинсы?

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

Отец: мы отправляемся в Манчестер (мы едем из Ньюкасла). Мать: мы не отправляемся в Манчестер, а едем из Ньюкасла (мы не остановились в Ливерпуле и едем из Ньюкасла).

Дочь: мы не едем из Ньюкасла (мы остановились в Ливерпуле). Следует ли студенту садиться в эту машину?

Льюис Кэрролл, автор широко известной книги «Алиса в Стране чудес» (менее известно, что он был математиком), любил задавать следующую задачу из четырёх фраз: «Из двух одно: или злоумышленник уехал в экипаже, или свидетель ошибся. Если злоумышленник имел сообщника, то он уехал в экипаже. У злоумышленника не было ни сообщника, ни ключа; или у него был сообщник и был ключ. У злоумышленника был ключ». Какой вывод отсюда можно сделать?

Профессор экономики сформулировал студентам три правила: