2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 Матлогика. Найти все следствия 2-х формул.
Сообщение22.12.2006, 17:37 


22/12/06
5
Задача формулируется так:
"Найдите ВСЕ логические следствия данных формул: (x*y)-->z , x+y"
Здесь Знаками +,*,--> я обозначил конъюнкцию, дизъюнкцию и импликацию.
Вопров: как можно найти ВСЕ логические следствия? Неужели их будет конечное число?[/math]

 Профиль  
                  
 
 
Сообщение27.12.2006, 01:56 
Аватара пользователя


01/12/06
697
рм
В исчислении высказываний если (A-->B) - тавтология, то говорят "A логически влечет B" или "B является логическим следствием A" (см. Э. Мендельсон, стр. 25).
В качестве «A» мы имеем две формулы, для которых можно составить истинностные таблицы. Учитывая что (A-->B) – тавтология, таблица для «B» будет давать на выходе значение «истина» во всех тех строках, в которых «A» дает «истина» и возможно ещё в других строках.
На пример, x+y (конъюнкция атомов «x» (1100) и «y» (1010)), в качестве формулы «A», имеет в столбце значений 1000. Тогда формула «B» должна иметь обязательно значение 1 (истина) в первой строке и возможно в некоторых других, включая случай когда «B» тавтология. Но тавтологий бесконечное множество. Возьми тавтологическую формулу
x-->x в качестве «B» и подставь на место «x» любую формулу «C», получишь снова тавтологию.
Так что о конечном числе формул «B» здесь говорить явно не приходится.
Я бы сформулировал эту задачу так (для формулы x+y):
Найти формулы (B) столбцы значений которых имеют вид:
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 (заметь, на первом месте стоит 1).
На пример, для столбца 1001 получаем дизъюнктивную нормальную форму
(x+y)*(~x+~y),
а также конъюнктивную нормальную форму
(~x*y)+(x*~y). Здесь ~ - отрицание.
Те же формы можно найти для остальных столбцов (см. Э. Мендельсон, стр. 31, 32).

Хотя я и знаю университетский курс «Исчисление высказываний» достаточно хорошо, все же я не математик по специальности. Поэтому советую обратиться также к специалистам или к более сильным студентам.

Если ты учишься на математика, то у меня, в свою очередь, тоже есть вопрос. Обсуди его с преподавателем по математической логике.
«Почему присоединение к исчислению высказываний пропозициональной формулы А в качестве аксиомы (а не схемы аксиом) тогда и только тогда нарушает простую непротиворечивость, когда А является тождественно ложной формулой?»
Об этом сказано в книгах Клини «Введение в метаматематику» (на стр. 123, сноска 1) и Чёрча «Введение в математическую логику» (на стр. 401, примечание 223), но их доводы (для меня) недостаточны, чтобы полностью понять это предложение, хотя с ним я в принципе согласен.
Если сможешь, помоги. Буду очень признателен.

Андрей

 Профиль  
                  
 
 
Сообщение08.01.2007, 17:55 
Аватара пользователя


01/12/06
697
рм
Никита1985, отзовись, прошу тебя.

 Профиль  
                  
 
 
Сообщение12.01.2007, 17:33 


22/12/06
5
Извини, давно не заходил.

Насчёт всех следствий я узнал у преподши. В общем все возможные следствия получаются как всевозможные перестановки переменных в СДНФ, составленной для конъюнкции всех исходных формул.

Постараюсь узнать насчёт твоего вопроса у преподавателей. К сожалению сейчас сдаю сессию, поэтому не могу точно сказать когда их увижу. :(

PS: Кстати, что такое "пропозициональной"?

 Профиль  
                  
 
 
Сообщение17.01.2007, 14:14 
Аватара пользователя


01/12/06
697
рм
пропозициональная формула = формула исчисления высказываний.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group