Форум программистов, компьютерный форум, киберфорум
Наши страницы
Мат. логика и множества
Войти
Регистрация
Восстановить пароль
 
Kaligulaa
5 / 6 / 2
Регистрация: 18.05.2015
Сообщений: 124
1

Доказательство теоремы. Исчисление высказываний

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

Доказать, что каждая из пар связок http://www.cyberforum.ru/cgi-bin/latex.cgi?\rightarrow ,\vee и http://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv , - не являются достаточной для выражения любой истинностной функции
Для примера рассмотрел http://www.cyberforum.ru/cgi-bin/latex.cgi?(A\vee A)\rightarrow A
Составим таблицу истинности
http://www.cyberforum.ru/cgi-bin/latex.cgi?A| \vee| \rightarrow
http://www.cyberforum.ru/cgi-bin/latex.cgi?T|T|T
http://www.cyberforum.ru/cgi-bin/latex.cgi?F|F|T
Это все равно, что представить это как форму http://www.cyberforum.ru/cgi-bin/latex.cgi?A\vee \bar A \equiv (A\vee A)\rightarrow A, но ее недостаточно для выражения http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar A, значит не всякую истинностную функцию можно построить с помощью данных двух связок.
Есть ли ошибки в рассуждениях? Поправьте , если что-то не так
А вот вторая задача
Интерпретируем связки следующим образом http://www.cyberforum.ru/cgi-bin/latex.cgi?f(A)=\bar (A \equiv A)
Таблица
http://www.cyberforum.ru/cgi-bin/latex.cgi?A|F(A)
http://www.cyberforum.ru/cgi-bin/latex.cgi?T|F
http://www.cyberforum.ru/cgi-bin/latex.cgi?F|F
Аналогично можно рассуждать и прийти к такому выводу? Правильные ли рассуждения? и кстати почему с помощью
отрицания нельзя выразить любую истинностную функцию? Что мешает?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2016, 20:39
Ответы с готовыми решениями:

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

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

Исчисление высказываний
Пожалуйста, если кто может помогите, очень нужно к контрольной работе,а я...

Доказательство теоремы
Здравствуйте. Объясните, пожалуйста, подробно доказательство следующей...

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

1
Mysterious Light
Эксперт по математике/физике
4007 / 1970 / 401
Регистрация: 19.07.2009
Сообщений: 2,990
Записей в блоге: 21
08.03.2016, 21:50 2
Оформите, пожалуйста, Ваше решение более строго, чтобы мы могли проверить, правильно ли оно или нет.

В нынешнем виде Ваше решение мне представляется таким:
Хотим: Доказать, что пары связок не достаточно для выражения любой истинностной функции.
1. Рассмотрим конкретную функцию X одного аргумента, составленную из связок.
2. Докажем, что X не является отрицанием.
3. Сделаем вывод, что найдётся истинностная функция (я так понимаю, отрицание), что никакая функция, составленная из связок, не выражает её.
Мне кажется, что пункт 3 требует обоснования. Обратите внимание на выделенные курсивом слова.

Добавлено через 57 секунд
P.S. отрицание в LaTeX обозначается \neg или \overline{ ... }
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.03.2016, 21:50

Исчисление высказываний. Мендельсон
Теорема: Единственными бинарными связками, каждой из которых можно построить...

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

Доказательство теоремы о транзитивном замыкании
Добрый день! Помогите пожалуйста понять доказательство: ...


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

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

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