Публикации: Логика

Алгоритмически неразрешимые проблемы.

Некоторые из них нам уже известны: 1. Проблема распознавания характера формулы в ЛП (ИП). 2. Алгоритмическая разрешимость проблемы нахождения корней уравнения степени выше 4. 3. К этим же проблемам относится проблема распознания самоприменимости машины Тьюринга; проблема ставится так: на ленте машины Тьюринга в терминах внешнего алфавита записана программа данной машины. Применима ли машина к полученной конфигурации? Алгоритма распознавания нет. 4. Проблема существования целых корней так называе... [читать дальше]

Основные элементарные АФ. Рекурсивные функции.

1) Идея рекурсии, т.е. построения новых объектов за счет уже некоторых нам известных (понятие формул в ИВ, построение выводимых формул в ИВ и т.д.). Понятие рекурсивных функций близко по идее: задается набор некоторых элементарных арифметических функций и набор некоторых правил построения новых функций на основе уже построенных. Такие правила называют здесь операторами. За счет этих правил, применяемых по началу к основным элементарным функциям, а затем и к вновь построенным, мы будем расширять... [читать дальше]

Семантика ИВ. Теоремы полноты и адекватности.

Метатеоремы – это теоремы о самой теории, в нашем случае АВ и ИВ. 1) Метатеоремы АВ. а) АВ не противоречива, в том смысле, что, никакое высказывание не может быть одновременно истинным и одновременно ложным, более того, никакая формула не может быть одновременно тавтологией и опровержимой. б) АВ полна, в том смысле, что о каждой формуле можно судить, является ли она тавтологией или нет. в) Более того, существует механизм определения характера формулы (таблицы истинности). В этом смысле АВ называ... [читать дальше]

Проблема разрешимости логики предикатов.

1) Постановка проблемы: Существует ли алгоритм, который позволял бы по виду формулы логики предикатов судить о том, каков ее характер (например, тавтология это или формула всего лишь выполнима). Как доказано (в 1936 г., Черч), проблема имеет отрицательный ответ, т.е. логика предикатов неразрешима. 2) Причина неразрешимости состоит в наличии бесконечных предметных областей и, вообще говоря, различное поведение формулы на бесконечном и конечном множествах. Так, например, существует формула, выполн... [читать дальше]

Тавтологии в логике предикатов.

1) Теорема 1. Всякая тавтология АВ, в которую вместо 0-местных предикатных переменных подставлены любые предикатные переменные n, m-местные, являются тавтологией в логике предикатов. Доказательство. Любая тавтология Е из АВ принимает значение истины при любом наборе значений, входящих в нее пропозиционных переменных. Следовательно, если любые из них (понимая теперь как 0-местные предикатные переменные) заменить на n, m-местные переменные, то всякая интерпретация такой формулы на любом множестве... [читать дальше]

Кванторные операции над предикатами

1) Пусть Р(х) – одноместный предикат, заданный на М. Операция связывания квантор общности предиката Р состоит в получении высказывания, которое по определению истинно, если Р(х) тождественно истинен на М, и ложно иначе. Это новое высказывание обозначим хР(х) («для любого хР(х)»,  - «квантор общности»). хР(х) = истина, если Р(х) тождественно истинен на М; ложь, если Р(х) опровержим. Пример 1. М≡R; Р(х): «х2>0» (опровержим), хР(х) =ложь. Операция связывани... [читать дальше]

Правильные и полные дизъюнкты и конъюнкты

1) Конъюнктивный одночлен (конъюнкт), а также дизъюнктивный одночлен (дизъюнкт) называют правильными , если они не содержат в своем составе более одного раза любую переменную xjσj. Это означает, что всякая переменная может входить в него ровно один раз, и одночлен не может содержать никакой переменной вместе с ее отрицанием.(правильный коньюнкт xКyКz) Ясно, что любой одночлен можно преобразовать правильно на основе основных равносильностей. 2) Предположим, что задан набор пропозиционных пер... [читать дальше]

Логические операции над высказываниями

Наполним смыслом введенную выше символику. Будем называть высказыванием всякое повествовательное предложение, о содержании которого известно, истинно оно или ложно. Отрицанием┐P высказывания P называется новое высказывание, которое истинно тогда и только тогда, когда P ложно («не P»). P ┐P И Л Л И Операцией перехода от P к ┐P называется операция отрицания. ДизъюнкциейP\/Q (“P или Q”) называется новое высказывание, которое истинно тогда и только тогда когда и... [читать дальше]

Понятие формулы алгебры высказывания

Алфавит алгебры высказываний (АВ). Рассмотрим совокупность некоторых объектов, которые будем называть высказываниями. Эти объекты будут обозначаться A, B или x, y, а сами символы будут называться пропозиционными переменными или атомами. Совокупность пропозиционных переменных обозначим G1. Алфавит есть множество, полученное объединениями 3 множеств: G=G1 U G2 U G3, где G2={┐, \/, /\} (логические связки), G3 – множество вспомогательных символов: скобки, запятые. Любая упорядоченная конечная... [читать дальше]

Логические нормы постановки вопроса и ответа

1. Вопрос должен быть корректно поставлен. Каверзные, провокационные и неопределенные вопросы недопустимы. 2. Вопрос должен быть простым, кратким, ясным, четким. Длинные, запутанные вопросы затрудняют их понимание, усложняют ответ на них. 3. В сложных разделительных вопросах необходимо перечислять все члены деления (альтернативы). 4. Вопрос не суждение, поэтому не следует приписывать ему характеристики суждения. Ответ должен быть: 1. четким, ясным, определенным; 2. информативным; 3. непротивореч... [читать дальше]