Форум программистов, компьютерный форум, киберфорум
Наши страницы

Мат. логика и множества

Войти
Регистрация
Восстановить пароль
 
Kaligulaa
4 / 4 / 1
Регистрация: 18.05.2015
Сообщений: 117
#1

Исчисление высказываний. Мендельсон. Ремейк темы - Логика и множества

08.03.2016, 23:39. Просмотров 180. Ответов 1
Метки нет (Все метки)

Еще раз здравствуйте, подобная тема уже появлялась в этой ветке.
Хочу полностью переформулировать свою проблему по теме доказательства теоремы из учебника Эллиота Мендельсона "Введение в математическую логику". Создаю новую тему для того, чтобы люди не участвовавшие в обсуждении смогли прояснить ситуацию и тоже высказаться.
И так
Теорема:
Единственными бинарными связками, каждой из которых достаточно для построения всех истинностных функций, являются связки стрелка Пирса и штрих Шеффера
Доказательство:
Предположим , что http://www.cyberforum.ru/cgi-bin/latex.cgi?h(A,B) является достаточной в указанном смысле связкой. Если бы http://www.cyberforum.ru/cgi-bin/latex.cgi?h(True,True) было http://www.cyberforum.ru/cgi-bin/latex.cgi?True, то любая пропозициональная форма, построенная с помощью лишь http://www.cyberforum.ru/cgi-bin/latex.cgi?h, принимала бы значение http://www.cyberforum.ru/cgi-bin/latex.cgi?True, когда все входящие в нее пропозициональные буквы принимают значение http://www.cyberforum.ru/cgi-bin/latex.cgi?True. Следовательно http://www.cyberforum.ru/cgi-bin/latex.cgi?\neg A не могла бы быть выражена только через http://www.cyberforum.ru/cgi-bin/latex.cgi?h. Итак http://www.cyberforum.ru/cgi-bin/latex.cgi?h(True,True)=False. Аналогично получаем , что http://www.cyberforum.ru/cgi-bin/latex.cgi?h(False,False)=True. Таким образом , мы имеем таблицу:
http://www.cyberforum.ru/cgi-bin/latex.cgi?A|B|h(A,B)
http://www.cyberforum.ru/cgi-bin/latex.cgi?T|T|F
http://www.cyberforum.ru/cgi-bin/latex.cgi?T|F|
http://www.cyberforum.ru/cgi-bin/latex.cgi?F|T|
http://www.cyberforum.ru/cgi-bin/latex.cgi?F|F|T
Если второе и третье места в столбце значений h этой таблицы заняты соответственно значениями T,T или F,F то получаем связку штрих Шеффера или стрелку Пирса. Если же на этих местах стоят F,T или T,F то формы http://www.cyberforum.ru/cgi-bin/latex.cgi?h(A,B)\equiv \neg B и соответственно http://www.cyberforum.ru/cgi-bin/latex.cgi?h(A,B)\equiv \neg A оказываются тавтологиями. В обоих случаях h выражена через http://www.cyberforum.ru/cgi-bin/latex.cgi? \neg . Однако связка http://www.cyberforum.ru/cgi-bin/latex.cgi? \neg не является достаточной в рассматриваемом смысле, поскольку единственными истинностными функциями от одной переменной, которые могут быть выражены через http://www.cyberforum.ru/cgi-bin/latex.cgi? \neg , являются функция, тождественно равная самой переменной, и отрицание переменной, а , например , функция тождественно равная T, не выразима через отрицание.


Ну и собственно куча вопросов возникает у меня:
1.
Если бы http://www.cyberforum.ru/cgi-bin/latex.cgi?h(True,True) было http://www.cyberforum.ru/cgi-bin/latex.cgi?True, то любая пропозициональная форма, построенная с помощью лишь http://www.cyberforum.ru/cgi-bin/latex.cgi?h, принимала бы значение http://www.cyberforum.ru/cgi-bin/latex.cgi?True, когда все входящие в нее пропозициональные буквы принимают значение http://www.cyberforum.ru/cgi-bin/latex.cgi?True.
А собственно почему так-то? Разве http://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow A не принимает истинное значение если http://www.cyberforum.ru/cgi-bin/latex.cgi?A =False. Тогда с вышеупомянутым трудно согласиться.
2.
Следовательно http://www.cyberforum.ru/cgi-bin/latex.cgi?\neg A не могла бы быть выражена только через http://www.cyberforum.ru/cgi-bin/latex.cgi?h.
Чем же это обосновать? Да, интуитивно это так, но строгости я не вижу, да и пример не приводится никакой здесь.
Сам приведу http://www.cyberforum.ru/cgi-bin/latex.cgi?A&A, ну действительно :
http://www.cyberforum.ru/cgi-bin/latex.cgi?A|h(A)
http://www.cyberforum.ru/cgi-bin/latex.cgi?T|T
http://www.cyberforum.ru/cgi-bin/latex.cgi?F|F
И вправду, невозможно тут никак получить инверсное значение аргумента, но почему так происходит в доказательстве не вижу обоснований
3.
...являются функция, тождественно равная самой переменной, и отрицание переменной, а , например , функция тождественно равная T, не выразима через отрицание.
Простите, а по-русски теперь? Если бы у бабушки была борода, то она была бы дедушкой.
Почему не выразима-то?
А два раза проинвертирую аргумент если?
http://www.cyberforum.ru/cgi-bin/latex.cgi?h(A,B)=\neg (\neg A)
Вполне себе могу конечно же получить True, однако интуитивно понятно уже, что действительно ничего не выразишь ей: даже например дизъюнкцию

Прошу Вас очень, разжуйте мне эту теорему, может быть я мыслю как-то не так легко, как может быть.
Заранее благодарю
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2016, 23:39
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Исчисление высказываний. Мендельсон. Ремейк темы (Логика и множества):

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

Исчисление высказываний - Логика и множества
Нужно вывести формулу (A \Rightarrow B) \rightarrow ((A*C)\Rightarrow(B*C)) Есть люди которые знакомы с данной темой и знают что надо...

исчисление высказываний - Логика и множества
Помогите пожалуйста. Не разобрался на лекции. Доказать в исчислении высказывании a=>a используя аксиомы. Если можно с комментариями....

Исчисление высказываний - Логика и множества
Пожалуйста, если кто может помогите, очень нужно к контрольной работе,а я ничего в этом предмете не понимаю. Доказать выводимость:

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

Исчисление высказываний (гильбертовского типа) - Логика и множества
Что-то выпал с 2х задачек 1.) Есть посылки: 1.) F-->G ; 2.) G-->F из них вывести F==G (== - тожество) Расписываю я это тождество по...

1
3D Homer
1375 / 897 / 301
Регистрация: 01.09.2014
Сообщений: 2,153
09.03.2016, 01:09 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Если бы h(True,True) было True, то любая пропозициональная форма, построенная с помощью лишь h, принимала бы значение True, когда все входящие в нее пропозициональные буквы принимают значение True.
Цитата Сообщение от Kaligulaa Посмотреть сообщение
1. А собственно почему так-то? Разве http://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow A не принимает истинное значение если http://www.cyberforum.ru/cgi-bin/latex.cgi?A =False.
Утверждение в учебнике следующее: любая формула, построенная только из h, принимает значение T, если все аргументы есть T. Если вы хотите опровергнуть это утверждение, то вам нужно найти формулу, построенную только из h, которая принимает значение F, если все аргументы есть T. При чем здесь импликация? Какое отношение имеет то, что A -> A равна T, если для опровержения вам нужно предъявить формулу, равную F на наборе аргументов из T? Ваше возражение похоже на следующее. Я утверждаю, что все числа, кратные 4, четные. Вы же говорите, что 26 тоже четное. Ну и что?

Чтобы понять интуитивно, почему каждая формула, построенная из h, принимает значение T, когда все аргументы равны T, постройте пять формул из h от разного количества аргументов и вычислите значение этих формул на T. Все это, конечно, в предположении, что h(T, T) = T. Формально факт из учебника доказывается индукцией по формуле из h, или индукцией по количеству связок в такой формуле.

Следовательно http://www.cyberforum.ru/cgi-bin/latex.cgi?\neg A не могла бы быть выражена только через h.
Цитата Сообщение от Kaligulaa Посмотреть сообщение
2. Чем же это обосновать?
Формула http://www.cyberforum.ru/cgi-bin/latex.cgi?\neg A, где A — это пропозициональная переменная, не обладает свойством, что если все переменные равны T, то и формула равна T. В то же время все формулы, построенные из h, удовлетворяют этому свойству. Следовательно, http://www.cyberforum.ru/cgi-bin/latex.cgi?\neg A не может быть построена из h.

Цитата Сообщение от Kaligulaa Посмотреть сообщение
Да, интуитивно это так, но строгости я не вижу, да и пример не приводится никакой здесь.
Это универсальное утверждение: любая формула, построенная только из h, не эквивалентна отрицанию. Универсальные утверждения не доказываются примерами.

Однако связка http://www.cyberforum.ru/cgi-bin/latex.cgi?\neg не является достаточной в рассматриваемом смысле, поскольку единственными истинностными функциями от одной переменной, которые могут быть выражены через http://www.cyberforum.ru/cgi-bin/latex.cgi?\neg , являются функция, тождественно равная самой переменной, и отрицание переменной, а , например , функция тождественно равная T, не выразима через отрицание.
Это тоже, строго говоря, доказывается индукцией по формуле. Простейшая формула — это переменная. При навешивания отрицания на формулу, эквивалентную переменной x, получается http://www.cyberforum.ru/cgi-bin/latex.cgi?\neg x и наоборот. Таким образом, других функций выразить невозможно.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.03.2016, 01:09
Привет! Вот еще темы с ответами:

Доказательство теоремы. Исчисление высказываний - Логика и множества
Доказать, что каждая из пар связок \rightarrow ,\vee и \equiv , - не являются достаточной для выражения любой истинностной функции Для...

Исчисление высказываний - показать, как решать - Логика и множества
Есть задание 4,5. Нужно показать, как решать примеры такого типа. Хотя бы пару букв. Теория есть, а примеров решений нет. ...

Исчисление данного высказывания - Логика и множества
Здравствуйте! Помогите в исчислением данного высказывания: (A -> (A -> (A -> A) ) ) С аксиомами. Заранее...

Исчисление предикатов методом резолюций - Логика и множества
Здравствуйте, не могли бы пожалуйста подсказать как решается данный пример. Вот задание: Доказать, что в исчислении предикатов выводимы...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru