Доказать невыразимость конъюнкции через дизъюнкцию и импликацию

Автор темы zklb (Дмитрий) 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеПремия Breakthrough Prize in Mathematics присуждена за «теорему о волшебной палочке»06.11.2019 16:07
18.10.2019 11:53
Доказать невыразимость конъюнкции через дизъюнкцию и импликацию
Из задачника по матлогике: доказать, что нельзя с помощью суперпозиции выразить & через V и ->.
Давно ещё всплывала она на dxdy, но там вопрошающему не помогли. В сам деле - все три функции сохраняют единицу, то есть лежат в одном классе и куда копать дальше - неведомо.
Тоже вертел задачку со всех сторон и придумал следующее:

Предположим, что существуют, выражаемые через V и -> бинарные функции f(x,y), задающие &, т.е. f(0,0) = 0, f(1,0) = f(0,1) = 0, f(1,1) = 1. Тогда среди них можно выбрать функцию f*(x,y) минимальной длины (по числу операций, скобок и переменных). Данную функцию можно представить в двух видах:
1) f*(x,y) = g(x,y) V h(x,y);
2) f*(x,y) = g(x,y) -> h(x,y),
где g(x,y) и h(x,y) - две другие функции.
Рассмотрим каждый случай:
1)
f*(0,0) = g(0,0) V h(0,0) = 0 ==> g(0,0) = h(0,0) = 0.
f*(0,1) = g(0,1) V h(0,1) = 0 ==> g(0,1) = h(0,1) = 0.
f*(1,0) = g(1,0) V h(1,0) = 0 ==> g(1,0) = h(1,0) = 0.
f*(1,1) = g(1,1) V h(1,1) = 1 ==> g(1,1) = 1 или h(1,1) = 1.
Таким образом одна из функций g или h должна являться функцией из класса f,задающих &. Но длина g и h меньше, чем у функции f*. Получили противоречие.
2)
f*(0,0) = g(0,0) -> h(0,0) = 0 ==> g(0,0) = 1, h(0,0) = 0.
f*(0,1) = g(0,1) -> h(0,1) = 0 ==> g(0,1) = 1, h(0,1) = 0.
f*(1,0) = g(1,0) -> h(1,0) = 0 ==> g(1,0) = 1, h(1,0) = 0.
f*(1,1) = g(1,1) -> h(1,1) = 1 ==> g(1,1) = 0, h(1,1) = 0 или g(1,1) = 0, h(1,1) = 1 или g(1,1) = 1, h(1,0) = 1.
Cлучай g(1,1)=0 невозможен, т.к. g - это суперпозиция функций V и -> (или они сами), а эти функции и их композиции сохраняют единицу. В двух последних случаях функция h является функцией из класса f,задающих &. Но её длина меньше, чем у функции f*. Получили снова противоречие.

Таким образом не существует минимальной функции f*, реализующей операцию & через V и ->, а значит, такой функции не существует вообще.

Вроде всё верно. Но можно ли проще?



Редактировалось 2 раз(а). Последний 19.10.2019 03:35.
18.10.2019 15:50
хм
А вот сам и нашёл небольшой пробел)
Фраза "Данную функцию можно представить в двух видах:
1) f*(x,y) = g(x,y) V h(x,y);
2) f*(x,y) = g(x,y) -> h(x,y),"
верна лишь отчасти. Исключение составляют случаи, когда g или h представляют собой отдельные переменные x или y. Но для каждого такого случая можно показать, что он невозможен, найдя набор значений x и y, приводящий к противоречию. Например:
Пусть f*(x,y) = x V h(x,y), тогда f*(1,0) = 0, но 1 V h(1,0) = 1.
Или пусть f*(x,y) = y -> h(x,y), тогда f*(1,0) = 0, но 0 -> h(1,0) = 1.



Редактировалось 1 раз(а). Последний 18.10.2019 15:52.
25.10.2019 14:54
От противного
Допустим представление возможно.
Рассмотрим наименьшее по числу операций.
Представим его в виде графа, на вход он получает векторы $[0, 0, 1, 1]$ и $[0, 1, 0, 1]$, а на выходе получается вектор $[0, 0, 0, 1]$.
Рассмотрим последний узел графа и его входные дуги.
Так как все используемые операции сохраняют единицу, то векторы на его входных дугах имеют единицы в качестве последнего элемента.
Если последний узел это V, то все остальные элементы равны 0; если последний узел импликация, то остальные элементы второго вектора равны 0. В любом случае по одной из дуг приходит $[0, 0, 0, 1]$, а значит представление не наименьшее.
Формулами наверное можно покороче выписать.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти