2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Выразить булевы функции из неполной системы функций
Сообщение21.10.2012, 21:44 
Аватара пользователя
Задана булева фунция $F(A, B, C) = C \vee AB \vee \overline{A \vee B} = 1 \oplus A \oplus B \oplus AC \oplus BC$. Вот для наглядности её таблица истинности:

$\begin{tabular}{|c|c|c||c|}
\hline
A & B & C & F \\
\hline
0 & 0 & 0 & 1\\
\hline
0 & 0 & 1 & 1\\
\hline
0 & 1 & 0 & 0\\
\hline
0 & 1 & 1 & 1\\
\hline
1 & 0 & 0 & 0\\
\hline
1 & 0 & 1 & 1\\
\hline
1 & 1 & 0 & 1\\
\hline
1 & 1 & 1 & 1\\
\hline
\end{tabular}$

Функция $F$ входит только в один класс Поста — в $T_1$, т. е. сохраняет единицу. Нужно из функции $F$ (ну, если быть точным, то из системы функций $\{F\}$) выразить все булевы функции нуля, одной и двух переменных, какие только можно.

$(F \notin T_0) \& (F \in T_1)$, поэтому легко можно выразить константу 1: $F(A, A, A) = 1$. Далее, подставляя единицу вместо одной, двух или всех трёх переменных в полиноме Жегалкина для этой функции, в 7 из 8 случаях получается единица, а в одном — дизъюнкция:
$\\
F(1, x, y) = 1 \oplus 1 \oplus x \oplus y \oplus xy = x \oplus y \oplus xy = x \vee y\\
x \vee y = F(F(A, A, A), x, y)
$

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

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group