Банк задач по математике

Задача 141

Доказать, что из формулы $Φ$ следует формула $\Psi$ тогда и только тогда, когда $\Phi \wedge \Psi \equiv \Phi$ , тогда и только тогда, когда $\Phi \vee \Psi \equiv \Psi . \quad \circledast$

?

Задача 142

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

?

Задача 143

(а)(б)(в)(г)

Назовём логическим произведением формулу, имеющую вид $\Phi_{1} \wedge \Phi_{2} \wedge \ldots \wedge \Phi_{n}$ . Её подформулы $\Phi_{i}, 1 \leqslant i \leqslant n$ , будем называть сомножителями. Аналогично, логической суммо й назовём формулу вида $\Phi_{1} \vee \Phi_{2} \vee \ldots \vee \Phi_{n}$ . Её подформулы $\Phi_{i}$ , $1 \leqslant i \leqslant n$ , будем называть слагаемыми.

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

?

(а)

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

(б)

если в логической сумме хотя бы одно из слагаемых равно 1, то и вся сумма равна 1;

(в)

если в логическом произведении $n \geqslant 2$ и есть сомножитель равный 1, то его можно вычеркнуть;

(г)

если в логической сумме $n \geqslant 2$ и есть слагаемое равное 0, то его можно вычеркнуть.

Задача 144

(а)(б)(в)

Используя основные тождества, доказать эквивалентность следующих пар формул.

?

(а)

$\neg (x \vee \neg y) \wedge (x \rightarrow \neg y)$ и $\neg x \wedge y$ ;

(б)

$\neg ((x \wedge \neg y) \rightarrow (\neg x \vee z))$ и $x \wedge \neg y \wedge \neg z$ ;

(в)

$(x \oplus y) \rightarrow (x \wedge \neg y)$ и $(\neg x \wedge \neg y) \vee x$ .

Задача 145

Вывести законы поглощения, используя предыдущие эквивалентности.

?

Задача 146

Доказать следующие эквивалентности:

?

(а)

$\Phi \rightarrow 0 \equiv \neg \Phi$ ;

(б)

$1 \rightarrow \Phi \equiv \Phi$ ;

(в)

$(\Phi \rightarrow \Psi ) \rightarrow \Psi \equiv \Phi \vee \Psi$ ;

(г)

$\neg \Phi \rightarrow \Phi \equiv \Phi$ ;

(д)

$(\Phi \rightarrow \Phi ) \rightarrow \Phi \equiv \Phi$ ;

(е)

$\Phi \leftrightarrow \Psi \equiv (\Phi \rightarrow \Psi ) \wedge (\Psi \rightarrow \Phi ) ;$

(ж)

$~ \Phi \vee (\neg \Phi \wedge \Psi ) \equiv \Phi \vee \Psi$ ;

(з)

$(\Phi \rightarrow \Psi ) \oplus (\Psi \rightarrow \Phi ) \equiv \Phi \oplus \Psi$ .

(и)

$\Phi \rightarrow (\Psi \vee \Theta ) \equiv (\Phi \wedge \neg \Theta ) \rightarrow \Psi$ ;

(к)

$(\Phi \wedge \Theta ) \rightarrow \Psi \equiv \Phi \rightarrow (\Psi \vee \neg \Theta )$ .

Задача 147

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

?

(а)

$(x \rightarrow (y \rightarrow x))$

(б)

$((x \wedge y) \rightarrow x)$

(в)

$(x \rightarrow (x \vee y))$

(г)

$((x \rightarrow \neg y) \rightarrow \neg (x \wedge y))$

(д)

$(((x \rightarrow y) \wedge (y \rightarrow z)) \rightarrow (x \rightarrow z))$

(е)

$(((x \rightarrow y) \vee (x \rightarrow z)) \rightarrow (x \rightarrow (y \vee z)))$

(ж)

$((x \rightarrow y) \rightarrow ((x \rightarrow \neg y) \rightarrow \neg x))$

(з)

$((x \rightarrow (y \rightarrow z)) \rightarrow ((x \rightarrow y) \rightarrow (x \rightarrow z)))$

Задача 148

Пусть интерпретация $J$ отличается от интерпретации $I$ только тем, что $J(x)=I(Θ)$ . Индукцией по построению формулы $\Phi$ доказать, что $J(\Phi )=I\left((\Phi )_{\Theta }^{x}\right)$ .

?

Задача 149

Доказать, что если $\Phi \equiv \Psi$ , то $(\Phi )_{\Theta }^{x} \equiv (\Psi )_{\Theta }^{x}$ .

?

Задача 150

(а)(б)

Пусть формулы $\Phi_{0}$ и $\Phi_{1}$ получены из формулы $\Phi$ заменой переменной $x_{i}$ на 0 и 1 соответственно. Доказать, что формула $\Phi$ эквивалентна любой из следующих:

?

(а)

$\left(\neg x_{i} \wedge \Phi_{0}\right) \vee \left(x_{i} \wedge \Phi_{1}\right) ;$

(б)

$\left(\neg x_{i} \rightarrow \Phi_{0}\right) \wedge \left(x_{i} \rightarrow \Phi_{1}\right)$ .

Задача 151

(а)(б)

Булева функция $f^{*}\left(x_{1}, \ldots , x_{n}\right)$ называется двойственной к функции $f\left(x_{1}, \ldots , x_{n}\right)$ , если $f^{*}\left(x_{1}, \ldots , x_{n}\right)=\neg f\left(\neg x_{1}, \ldots , \neg x_{n}\right)$ для каждого набора значений переменных. Например, конъюнкция двойственна к дизъюнкции и наоборот.

?

(а)

Доказать, что отношение двойственности симметрично.

(б)

Пусть $f\left(y_{1}, \ldots , y_{m}\right), g_{1}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}\left(x_{1}, \ldots , x_{n}\right)$ — булевы функции и

h\left(x_{1}, \ldots , x_{n}\right)=f\left(g_{1}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}\left(x_{1}, \ldots , x_{n}\right)\right).

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

h^{*}\left(x_{1}, \ldots , x_{n}\right)=f^{*}\left(g_{1}^{*}\left(x_{1}, \ldots , x_{n}\right), \ldots , g_{m}^{*}\left(x_{1}, \ldots , x_{n}\right)\right).

Задача 152

(а)(б)(в)(г)

Построить двойственные функции для функций

?

(а)

$\neg$ ,

(б)

→,

(в)

$\oplus$ ,

(г)

↑.

Задача 153

(а)(б)(в)

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

?

(а)

$(x \rightarrow \neg (\neg y \oplus x \oplus z))$ ;

(б)

$((x \uparrow y) \oplus (\neg x \rightarrow z))$ ; $\circledast$

(в)

$((x \vee \neg y) \rightarrow (\neg x \downarrow y))$ .

Задача 154

(а)(б)(в)

?

(а)

Доказать, что среди 20 формул от переменных $x_{1}, x_{2}$ всегда найдутся две эквивалентные.

(б)

Верно ли, что среди 20 формул от переменных $x_{1}, x_{2}$ всегда найдутся три попарно эквивалентные?

(в)

Пусть имеется $k$ формул от $n$ переменных $x_{1}, \ldots , x_{n}$ . Требуется выбрать несколько попарно эквивалентных формул. Какое количество таких формул можно гарантированно найти?

Задача 155

Назовём импликативной формулу $Φ$ (и определяемую ей функцию), которая получена какой-либо расстановкой скобок в строке $x_{1} \rightarrow x_{2} \rightarrow \cdots \rightarrow x_{n-1} \rightarrow x_{n}$ . Доказать, что

?

(а)

каждая импликативная формула принимает значение 1 как минимум на одном наборе;

(б)

каждая импликативная формула принимает значение 0 как минимум на одном наборе;

(в)

для каждой импликативной формулы с $n \geqslant 2$ переменными и каждого значения $\sigma_{k}$ переменной $x_{k}$ существует возможность расширить $\sigma_{k}$ до набора значений $\bar{\sigma }$ всех переменных, на котором формула имеет значение 1 ;

(г)

каждая импликативная функция не имеет фиктивных аргументов;

(д)

никакие две разные импликативные формулы не эквивалентны.

Задача 156

Доказать, что функция $f$ может быть получена из некоторой импликативной функции $g$ подстановкой переменных:

f\left(x_{1}, \ldots , x_{n}\right)=g\left(x_{i_{1}}, \ldots , x_{i_{m}}\right)

тогда и только тогда, когда $f$ задаётся формулой вида $x_{i} \vee \Psi$ для некоторой переменной $x_{i}$ .

?

Эквивалентность формул