Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Проблема повноти, несуперечності, розв'язності числення висловлювань. Незалежність аксіом числення висловлювань. ⇐ ПредыдущаяСтр 2 из 2
Полнота исчисления высказываний Теорема 1. Всякая выводимая в исчисления высказываний (ИВ) формула является тождественно истинная (тавтология) алгебры высказываний. Если |- F, то |= F (|= - тожд. истинная). Док-во. Пусть формула F выводима. Следовательно существует последовательность формул (В 1, В 2,…, В п = F). ? F – тавтология?? 1.n=1 Все аксиомы являются тавтологиями 2.S<= n (Все формулы с длиной s<=n являются тавтологией) 3.S= n+1 (В 1, В 2,…, В п, В п+1) В п+1 – может быть аксиомой, либо получена из 2 предшествующих формул (В i; В j) по MP В j =В i -> В п+1 Теорема 2. Всякая тождественно истинная формула алгебры высказываний выводима в исчислении высказываний. Если |= F, то |- F. Теорема (о полноте ИВ) Формула исчисления высказываний выводима в ИВ (является теоремой ИВ) тогда и только тогда,, когда она является тавтологией алгебры высказываний. Непротиворечивость ИВ Аксиоматическая теория наз. непротиворечивой, если ни для какого утверждения А, сформулированного в терминах этой теории, само утверждение А и его отрицание Ø А не могут быть одновременно теоремами данной теории. Теорема. ИВ непротиворечивая теория. Следует из теоремы о полноте. Формулы A и ØA одновременно не могут быть выводимыми. Разрешимость ИВ Аксиоматическая теория наз. разрешимой, если существует алгоритм, позволяющий для любого утверждения, сформулированного в терминах этой теории, ответить на вопрос, будет или нет это утверждение теоремой данной теории. Теорема. ИВ есть разрешимая теория. Независимость аксиом ИВ Аксиома А системы аксиом ∑ наз. Независящей от остальных аксиом этой системы, если её нельзя вывести из остальных аксиом этой системы (∑\{А}). №3. Алфавіт мови логіки предикатів. Визначення терма, формули мови першого порядку. Вільні та зв'язані входження змінних. Терм, вільний для змінної у формулі. n-местным предикатом, определенным на множествах , ,…, , называется предложение, содержащее n переменных , ,…, и превращающееся в высказывание при подстановке вместо этих переменных конкретных высказываний из множеств , ,…, соответственно. Множеством истинности предиката , заданного на множествах , ,…, , называется совокупность всех упорядоченных n систем таких, что при их подстановке предикат превращается в истинное высказывание .
Два предиката P и Q являются равносильными, если их множества истинности совпадают.
Алфавит языка теории первого порядка состоит из: 1. Предметные константы , , ,…, ,… 2. Предметные переменные , , , …, ,… 3. Функциональные символы (буквы из середины алфавита) , , ,…, , … 4. Предикатные символы , , ,…, , … 5. Символы логических операций , , , , , , 6. Вспомогательные символы (), Множество предметных констант Const, множество функциональных символов Fn, множество предикатных символов Pr образуют сигнатуру языка первого порядка. Основными конструкциями языка первого порядка являются термы и формулы.
Индуктивное определение терма: 1.Каждая переменная есть терм. 2.Каждая константа есть терм. 3.Если - это k-местный функциональный символ, а - термы, то - терм. (Правило порождения терма)
Элементарной (атомарной) формулой называется выражение , где - термы, а - n-местный предикатный символ.
Индуктивное определение формулы языка первого порядка: 1. Каждая элементарная формула есть формула. 2. Если - формула языка первого порядка, то - также формула. 3. Если , - формулы, то , , , - формулы. 4. Если - формула, а - переменная, то выражения , - также формулы. 5. Любое вхождение переменной в формулу или называется связанным вхождением переменной , а предметная переменная называется связанной. Сама формула называется областью действия соответствующего квантора по переменной . 6. Предметная переменная (вхождение предметной переменной) называется свободной (свободным вхождением), если она (оно) не находится в области действия квантора по этой переменной. 7. Формула, не содержащая свободных переменных, называется замкнутой. (подчеркнуто свободное вхождение) Терм свободен для переменной в формуле , если никакое свободное вхождение переменной в формулу не находится в области действия кванторов по переменным, входящим в терм . - свободен - не свободен
|
|||||
Последнее изменение этой страницы: 2016-04-08; просмотров: 258; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.93.162.26 (0.008 с.) |