Редактирование: Исчисление высказываний

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
[[Математическая логика | На главную <<]][[Лекция 3 | >>]]
 
 
[[Категория: Математическая логика]]
 
 
 
==Язык исчисления высказываний==
 
==Язык исчисления высказываний==
 
===Определения===
 
===Определения===
{{Определение
 
|definition=
 
Одним из базовых понятий логики высказываний является пропозициональная переменная — переменная, значением которой может быть логическое высказывание
 
}}
 
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 23: Строка 14:
 
<nowiki><пропозициональная переменная></nowiki> формально не определяется. Договоримся, что это - буква латинского алфавита (возможно, с нижним индексом).
 
<nowiki><пропозициональная переменная></nowiki> формально не определяется. Договоримся, что это - буква латинского алфавита (возможно, с нижним индексом).
 
}}
 
}}
 
 
===Расстановка скобок===
 
===Расстановка скобок===
 
Так построенная грамматика предписывает определенный способ расстановки
 
Так построенная грамматика предписывает определенный способ расстановки
Строка 55: Строка 45:
  
 
{{Определение
 
{{Определение
|definition=Если дано некоторое высказывание $\alpha$, в котором используются пропозициональные
+
|definition=<wikitex>Если дано некоторое высказывание $\alpha$, в котором используются пропозициональные
 
переменные $v_1 \dots v_n$, то ''оценку'' данного высказывания $|\alpha|$ мы определим  
 
переменные $v_1 \dots v_n$, то ''оценку'' данного высказывания $|\alpha|$ мы определим  
 
следующим рекурсивным образом.
 
следующим рекурсивным образом.
Строка 66: Строка 56:
 
* импликация выражений $\alpha$ и $\beta$: $f_\to (|\alpha|,|\beta|)$
 
* импликация выражений $\alpha$ и $\beta$: $f_\to (|\alpha|,|\beta|)$
 
* отрицание выражения $\alpha$: $f_\neg (|\alpha|)$
 
* отрицание выражения $\alpha$: $f_\neg (|\alpha|)$
* во всех остальных случаях оценка выражения равна оценке потомка в дереве.
+
* во всех остальных случаях оценка выражения равна оценке потомка в дереве.</wikitex>
 
}}
 
}}
  
Строка 89: Строка 79:
  
 
{{Определение
 
{{Определение
|id=valid
 
 
|definition=
 
|definition=
 
Назовем выражение общезначимым, если его оценка истинна при любой оценке входящих в него пропозициональных переменных. Запись: <tex>\models \alpha</tex>.
 
Назовем выражение общезначимым, если его оценка истинна при любой оценке входящих в него пропозициональных переменных. Запись: <tex>\models \alpha</tex>.
Строка 97: Строка 86:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Формальная система - упорядоченная тройка <tex>\langle L, A, R \rangle</tex>, где <tex>L</tex> --- некоторый язык, <tex>A \subset L</tex> --- множество аксиом, а <tex>R \subset (L^2 \cup L^3 \cup ...)</tex> - множество правил вывода
+
Формальная система - упорядоченная тройка <tex><L, A, R></tex>, где <tex>L</tex> --- некоторый язык, <tex>A \subset L</tex> --- множество аксиом, а <tex>R /subset (L^2 \cup L^3 \cup ...)</tex> - множество правил вывода
 
}}
 
}}
  
Строка 104: Строка 93:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Доказательство в формальной системе <tex>\langle L, A, R \rangle</tex> - конечная последовательность выражений <tex>\alpha_1, ..., \alpha_n</tex> из <tex>L</tex>, такая, что <tex>\forall i \le n</tex> либо <tex>\alpha_i \in A</tex>, либо <tex>\alpha_i</tex> получается с использованием правил вывода из предыдущих выражений.
+
Доказательство в формальной системе <tex><L, A, R></tex> - конечная последовательность выражений <tex>\alpha_1, ..., \alpha_n</tex> из <tex>L</tex>, такая, что <tex>\forall i \le n</tex> либо <tex>\alpha_i \in A</tex>, либо <tex>\alpha_i</tex> получается с использованием правил вывода из предыдущих выражений.
 
}}
 
}}
  
Строка 111: Строка 100:
 
Высказывание <tex>\alpha</tex> называется доказуемым, если существует доказательство <tex>\alpha_1, ..., \alpha_k</tex>, в котором <tex>\alpha_k == \alpha</tex>. Запись: <tex>\vdash \alpha</tex>.
 
Высказывание <tex>\alpha</tex> называется доказуемым, если существует доказательство <tex>\alpha_1, ..., \alpha_k</tex>, в котором <tex>\alpha_k == \alpha</tex>. Запись: <tex>\vdash \alpha</tex>.
 
}}
 
}}
 
Расширим грамматику из предыдущего раздела:
 
* <nowiki><выражение></nowiki> ::= <nowiki><импликация></nowiki><tex>| \psi | \phi | \pi</tex>
 
* <nowiki><импликация></nowiki> ::= <nowiki><дизъюнкция></nowiki> <tex>|</tex> <nowiki><дизъюнкция></nowiki> <tex>\rightarrow</tex> <nowiki><импликация></nowiki>
 
* <nowiki><дизъюнкция></nowiki> ::= <nowiki><конъюнкция></nowiki> <tex>|</tex> <nowiki><дизъюнкция></nowiki> <tex>\vee</tex> <nowiki><конъюнкция></nowiki>
 
* <nowiki><конъюнкция></nowiki> ::= <nowiki><терм></nowiki> <tex>|</tex> <nowiki><конъюнкция></nowiki> <tex>\&</tex> <nowiki><терм></nowiki>
 
* <nowiki><терм></nowiki> ::= <nowiki><пропозициональная переменная></nowiki> <tex>|</tex> (<nowiki><выражение></nowiki>)
 
 
Назовем <tex>\psi, \phi, \pi</tex> ''схемами выражений''. Если вместо ''всех'' данных букв подставить корректные выражения из грамматики, получим корректное выражение. При этом, одинаковые буквы должны меняться на одинаковые выражения.
 
 
 
{{Определение
 
|definition=
 
Все выражения, полученные из схемы путем подстановки выражений вместо букв <tex>\psi, \phi, \pi</tex>, назовем выражениями, '''порожденными''' схемой.
 
}}
 
 
{{Определение
 
|definition=
 
Исчисление высказываний - формальная система, использующая в качестве языка язык исчисления высказываний, в качестве аксиом - следующие схемы выражений:
 
#<tex>(\phi) \rightarrow ((\psi) \rightarrow (\phi))</tex>
 
#<tex>((\phi) \rightarrow (\psi)) \rightarrow ((\phi) \rightarrow (\psi) \rightarrow (\pi)) \rightarrow ((\phi) \rightarrow (\pi))</tex>
 
#<tex>(\phi) \rightarrow (\psi) \rightarrow (\phi) \& (\psi)</tex>
 
#<tex>(\phi) \& (\psi) \rightarrow (\phi)</tex>
 
#<tex>(\phi) \& (\psi) \rightarrow (\psi)</tex>
 
#<tex>(\phi) \rightarrow (\phi) \vee (\psi)</tex>
 
#<tex>(\psi) \rightarrow (\phi) \vee (\psi)</tex>
 
#<tex>((\phi) \rightarrow (\pi)) \rightarrow ((\psi) \rightarrow (\pi)) \rightarrow ((\phi) \vee (\psi) \rightarrow (\pi))</tex>
 
#<tex>((\phi) \rightarrow (\psi)) \rightarrow ((\phi) \rightarrow \neg (\psi)) \rightarrow \neg (\phi)</tex>
 
#<tex>\neg \neg (\phi) \rightarrow (\phi)</tex>
 
, а правила вывода - все правила, порожденные согласованной заменой букв в <tex>\langle{}\phi, (\phi) \rightarrow (\psi), \psi\rangle</tex>.
 
}}
 
 
[[Категория: Математическая логика]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: