@Kaligulaa

Теорема: Единственными бинарными связками, каждой из которых можно построить любую истинностную функцию являются штрих Шеффера и стрелка Пирса.

Ниже привожу абсолютно мне неясное доказательство данной теоремы, так, как изложено в учебнике "Введение в математическую логику" Э.Менедельсона:
Предположим, что является достаточной в указанном смысле связкой. Если было , то любая пропозициональная форма, построенная с помощью только лишь
принимала бы значение , когда все входящие в нее пропозициональные буквы принимают значение . Следовательно форма не могла бы быть выражена только через . Итак . Аналогично получаем ...

Не буду далее расписывать дальнейшее доказательство, так начиная с ясно, что делать дальше. Вопрос у меня о начале доказательства:
Следовательно форма не могла бы быть выражена только через .
Простите, а почему нет-то? Допустим возьмем , неужели ее будет недостаточно для построения[Простите, иначе не знаю как выразить в латексе отрицание всей формы]?
Например ,
ну разве нельзя вывести , если аргументы будут принимать разные значения или одновременно ложь? Или я чего-то не понимаю?


В сотый раз уже пытаюсь освоить курс матлогики по Э. Мендельсону.

0

@nworm

Не, недостаточно. Отрицания то нет. Есть только конъюнкция.

Объяснение в других терминах - класс функций, сохраняющих FALSE.
Эти функции на наборах из FALSE всегда дают FALSE.
И, как не пытайся подставлять их друг в друга, TRUE не получишь на наборе из FALSE.

1

@Kaligulaa

То есть, по Вашему, при подстановке TRUE TRUE мы никогда не получим FALSE? И наооборот

P.S. имею в виду рассуждать надо так: рассматривать на конкретном наборе значений TRUE TRUE

0

@nworm

Да. Для функций, сохраняющих TRUE - никогда.
Например,

1

@Kaligulaa

И снова возникает вопрос... Цитирую дальнейшее доказательство теоремы:
Таким образом, мы имеем таблицу:





Если второе и третье места в столбце значений этой таблицы заняты соответственно значениями и то мы получаем связку штрих Шеффера или стрелку Пирса.
[Ну хорошо, да, интуитивно ясно, и дополнять ничего не надо здесь..]
Если же на этих местах стоит и , то формы и соответственно оказываются тавтологиями. - Ну вот опять ничего не ясно!
Что это означает ? Что, например в связке нужно подставить вместо всех вхождений вхождения в первом случае? Тогда действительно получаем , что , по логике, действительно является тавтологией, так же можно сделать и для .
Далее:
В обоих случаях выражена через отрицание. И опять: что имеется в виду, что пропозициональная форма содержит отрицание или пропозициональная связка состоит только из отрицания?
Пожалуйста , поясните хотя бы на примерах что имелось в виду, или переформулируйте.

P.S. как же Мендельсон тяжело пишет...

Добавлено через 15 минут
Простите написал полный бред начиная с Переформулирую
Что это означает ? На примере какой связки-то? как из этой связки можно вообще получить ? Опять возьмем в пример , ну где же тут тавтология, что имели в виду, или автор так исключил полностью букву и построил с помощью связки отрицание такую форму?

0

@nworm

Это значит верны.
Другими словами.
Верны формулы и соответственно

Посмотрите, в первом случае таблица h вот такая:
A|B|h
T|T|F
F|T|F
T|F|T
F|F|T
Точно такая же как у функции

А во втором
A|B|h
T|T|F
F|T|T
T|F|F
F|F|T
Точно такая же как у функции

0

@Kaligulaa

Пожалуйста, переведите, что тут написано в конце доказательства

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

0

@nworm

Нельзя через связку все, все возможные формулы получить.
Потому что нельзя даже все функции от одной переменной получить. Из этой связки удалось только отрицание получить. А все функции одной переменной - никак. TRUE - не удаётся получить: отрицание - не TRUE, отрицание от отрицания - опять не TRUE.

0