Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2018-01-29 | 307 |
5.00
из
|
Заказать работу |
|
|
Используя понятие формального исчисления, определим исчисление высказываний (ИВ).
Алфавит ИВ состоит из букв А,В,Q,R,Р и других, возможно с индексами (которые называются пропозициональными переменными), логических символов (связок), ∧, ∨, →, а также вспомогательных символов (,).
Множество формул ИВ определяется индуктивно:
а)все пропозициональные переменные являются формулами ИВ;
б)если φ, ψ‑ формулы ИВ, то φ, (φ∧ψ), (φ∨ψ), (φ → ψ) – формулы ИВ;
в)выражение является формулой ИВ тогда и только тогда, когда это может быть установлено с помощью пунктов "а" и "б".
Таким образом, любая формула ИВ строится из пропозициональных переменных с помощью связок, ∧, ∨, →.
В дальнейшем при записи формул будем опускать некоторые скобки, используя те же соглашения, что и в предыдущей главе.
Подформулой ψ формулы φИВ называется подслово φ, являющееся формулой ИВ.
Под длиной формулы будем понимать число символов, входящих в слово φ.
Аксиомами ИВ являются следующие формулы для любыхформул φ, ψ, χ:
1) φ→(ψ→φ);
2) (φ→ψ)→((φ→(ψ→χ))→(φ→χ));
3) (φ∧ψ)→φ;
4) (φ∧ψ)→ψ;
5) (φ→ψ)→((φ→χ)→(φ→(ψ∧χ)));
6) φ→(φ∨ψ);
7) φ→(ψ∨φ);
8) (φ→χ)→((ψ→x)→((φ∨ψ)→χ));
9) (φ→ψ)→((φ→ψ)→φ);
10) φ→φ.
Указанные формулы называются схемами аксиом ИВ. При подстановке конкретных формул в какую-либо схему получается частный случай схемы аксиом.
Единственным правилом вывода в ИВ является правило заключения (modusponens): если φ и φ→ψ ‑выводимые формулы, то ψ‑ также выводимая формула. Символически это записывается так:
|
φ, φ→ψ
ψ
Говорят, что формула φ выводима в ИВ из формул φ1,…,φm (обозначается φ1,…,φm├φ), если существует последовательность формул ψ1,…,ψk,φ,в которой любая формула либо является аксиомой, либо принадлежит списку формул φ1,…,φm,называемых гипотезами, либо получается из предыдущих по правилу вывода. Выводимость формулы φ из (├φ) равносильна тому, что φ‑ теорема ИВ.
Пример 1. Покажем, что ├φ→φ.
Решение. Построим вывод данной формулы:
1)в схеме аксиом 2 ψ заменим на φ→φ,χ на φ. Получаем аксиому (φ→(φ→φ))→((φ→((φ→φ)→φ)→(φ→φ));
2)в схеме аксиом 1 ψ заменим на φ. Получаем φ→(φ→φ);
3)из 1 и 2 по правилу вывода заключаем (φ→((φ→φ)→φ))→(φ→φ);
4)в схеме аксиом 1 заменяем ψна φ→φ. Получаем φ→((φ→φ)→φ);
5)из пп. 3 и 4 по правилу вывода справедливо ├φ→φ.
Пример 2. Покажем, что φ,ψ├φ ψ
Решение: Построим вывод формул φ ψ из φ и ψ
1) φ (гипотеза);
2) ψ (гипотеза);
3) (φ→φ)→((φ→φ)→(φ→φ ψ)) (схема аксиом);
4) φ→φ (используем формулу из примера 13);
5) ((φ→ψ)→(φ→φ ψ)) (применим правило вывода к пунктам 4,3);
6) ψ→(φ→ψ) (схема аксиом);
7) φ→ψ (применим правило вывода к пунктам 2,6);
8) φ→φ ψ (применим правило вывода к п.п. 7,5);
9) φ ψ (применим правило вывода к п.п. 1,8).
Квазивыводом в ИВ формулы φ из формул φ1,…,φm называется последовательность формул ψ1,…,ψk,φ, в которой любая формула выводима из предыдущих.
Замечание 1. Если существует квазивывод в ИВ формулы φ из формул φ1,…,φm, то φ выводима в ИВ из формул φ1,…,φm.
Пример 3. Покажем, что φ├φ.
Решение. Построим квазивывод формулы φ из формулы φ:
1) φ (гипотеза);
2) (φ→φ)→((φ→φ)→φ) (схема аксиом 9);
|
3) φ→(φ→φ) (схема аксиом 1);
4) φ→φ (к пп. 1 и 3 применили правило вывода);
5) (φ→φ)→φ (к пп. 4 и 2 применили правило вывода);
6) φ→φ (по примеру 2 выводимая формула);
7) φ (к пп. 6 и 4 применили правило вывода).
|
|
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!