2.6: Резюме логіки першого порядку

16. Короткий зміст логіки першого порядку

16.1 Елементи мови

• Символічні терміни - це або імена, невизначені імена, змінні або довільні терміни.
  • Назви: а, б, в, д, е...
  • Невизначені назви: p, q, r...
  • Змінні: x, y, z...
  • Довільні терміни: x ′, y ′, z ′...
• Кожен присудок має арність, яка є кількістю символічних термінів, необхідних цим присудком для формування добре сформованої формули. Присудки нашої мови: F, G, H, I...
• Кожна функція має арність, яка є кількістю символічних термінів, необхідних функції для того, щоб вона утворила символічний термін. Функціями нашої мови є: f, g, h, i...
• Є два квантори.
  • , універсальний квантор.
  • , екзистенціальний квантор.
• З'єднувачі такі ж, як і у логіки пропозиції.

16.2 Синтаксис мови

• Рідність функції в поєднанні з n символічними термінами є символічним терміном.
• Рідність в присудку в поєднанні з n символічними членами - це добре сформована формула.
• Якщо Φ і ψ є добре сформованими формулами, то наступні також добре сформовані формули. (А якщо Φ і ψ є реченнями, то наступні також є реченнями.)
  • ¬ Φ
  • (Φ → ψ)
  • (Φ ^ ψ)
  • (Φ v ψ)
  • (Φ ↔ ψ)
• Запишемо Φ (α) на середнє Φ - це добре сформована формула, в якій фігурує символічний термін α.
• Якщо в Φ (x) немає кванторів, то x - це вільна змінна в Φ. (Імена ніколи не описуються як вільні.) Якщо для цієї формули Φ ми запишемо xφ (x) або xφ (x), ми говоримо, що х тепер пов'язаний у Φ. Змінна, яка пов'язана, не є вільною.
• Добре сформована формула без вільних змінних - це речення.

16.3 Семантика мови

• Семантика імен, предикатів та кванторів залишиться для нас інтуїтивною. Розширена логіка (з теорією множин) потрібна, щоб зробити їх більш точними. Ми говоримо:
  • Домен дискурсу - це сукупність предметів, про які йде наша мова.
  • Ім'я посилається на рівно один об'єкт з нашої області дискурсу.
  • Присудок парності n описує властивість або відношення n об'єктів.
  • x Φ (x) означає, що будь-який об'єкт у нашій області дискурсу має властивість Φ.
  • x Φ (x) означає, що принаймні один об'єкт у нашій області дискурсу має властивість Φ.
• Якщо Φ і ψ є пропозиціями, то значення сполучних повною мірою задаються їх таблицями істинності. Ці таблиці істини, що визначають семантику:

Φ	¬Φ
Т	F
F	Т

Φ	ψ	(Φ → ψ)
Т	Т	Т
Т	F	F
F	Т	Т
F	F	Т

Φ	ψ	(Φ ^ ψ)
Т	Т	Т
Т	F	F
F	Т	F
F	F	F

Φ	ψ	(Φ v ψ)
Т	Т	Т
Т	F	Т
F	Т	Т
F	F	F

Φ	ψ	(Φ ↔ ψ)
Т	Т	Т
Т	F	F
F	Т	F
F	F	Т

• Кожне речення має бути істинним чи хибним, ніколи не обидва, ніколи ні.
• Речення, яке повинно бути істинним, логічно вірно. (Речення нашої логіки, які мають ту ж форму, що і тавтології логіки пропозиції, ми все ще можемо назвати «тавтологіями». Однак є деякі речення логіки першого порядку, які повинні бути правдивими, але які не мають форми тавтологій логіки пропозиції. Приклади включають в себе: «х» (Ф х → Ф х ) і х (Ф х v ¬ F) х).)
• Речення, яке повинно бути помилковим, є суперечливим реченням.
• Речення, яке може бути істинним або може бути помилковим, є умовним реченням.
• Два речення Φ і ψ є «еквівалентними» або «логічно еквівалентними», коли (Φ ↔ ψ) є теоремою.

16.4 Міркування з мовою

• Аргумент - це упорядкований список пропозицій, одне речення якого ми називаємо «висновком», а інші з яких ми називаємо «приміщеннями».
• Допустимим аргументом є аргумент, в якому: обов'язково, якщо приміщення істинні, то висновок вірний.
• Звуковий аргумент - це вагомий аргумент з істинними передумовами.
• Правила висновку дозволяють нам записати речення, яке повинно бути істинним, припускаючи, що деякі інші речення повинні бути істинними. Ми говоримо, що речення походить від інших речень, використовуючи правило висновку.
• Схематично ми можемо виписати правила висновку наступним чином (подумайте про них як про те, якщо ви записали речення над рядком, то ви можете записати речення нижче рядка; також порядок пропозицій над рядком, якщо їх декілька, не має значення):

Модус полененс	Модус Толленс	Подвійне заперечення	Подвійне заперечення
(Φ → ψ) Φ _____ ψ	(Φ → ψ) ¬ψ _____ ¬Φ	Φ _____ ¬¬Φ	¬¬Φ _____ Φ
Додавання	Додавання	Модус Толлендо Поненс	Модус Толлендо Поненс
Φ _____ (Φ v ψ)	ψ _____ (Φ v ψ)	(Φ v ψ) ¬Φ _____ ψ	(Φ v ψ) ¬ψ _____ Φ
примикання	Спрощення	Спрощення	Біумова
Φ ψ _____ (Φ ^ ψ)	(Φ ^ ψ) _____ Φ	(Φ ^ ψ) _____ ψ	(Φ → ψ) (ψ → Φ) _____ (Φ ↔ ψ)
Еквівалентність	Еквівалентність	Еквівалентність	Еквівалентність
(Φ ↔ ψ) Φ _____ ψ	(Φ ↔ ψ) ψ _____ Φ	(Φ ↔ ψ) ¬Φ _____ ¬ψ	(Φ ↔ ψ) ¬ψ _____ ¬Φ
Повторити	Універсальний екземпляр	екзистенціальне узагальнення	Екзистенціальний екземпляр
Φ _____ Φ	αφ (α) _____ Φ (β)	Φ (β) _____ αφ (α)	αφ (α) _____ Φ (ψ)
	де β - будь-який символічний термін	де β - будь-який символічний термін	де ρ - невизначене ім'я, яке не відображається вище в жодному відкритому доказі

• Доказ (або деривація) - синтаксичний метод для показу аргументу є дійсним. Наша система має чотири види доказів (або деривації): пряме, умовне, непряме та універсальне.
• Пряме доказ (або пряме виведення) - це впорядкований список речень, в якому кожне речення є або передумовою, або походить від попередніх рядків, використовуючи правило висновку. Останній рядок доказу - висновок.
• Умовне доказ (або умовне деривація) - це упорядкований список пропозицій, в якому кожне речення є або передумовою, є спеціальним припущенням для умовного похідного, або походить від попередніх рядків за допомогою правила висновку. Якщо припущення для умовного деривації дорівнює Φ, і ми виведемо як якийсь крок у доведенні ψ, то ми можемо записати після цього (Φ → ψ) як наш висновок.
• Непрямим доказом (або непрямим похідним, а також відомим як reductio ad absurdum) є: впорядкований список речень, в якому кожне речення є або 1) передумовою, 2) спеціальним припущенням для непрямого похідного (також іноді називають «припущенням для скорочення»), або 3) похідним від раніше рядків, що використовують правило висновку. Якщо наше припущення про непряме виведення становить ¬ Φ, і ми виведемо як якийсь крок у доказі ψ, а також як якийсь крок нашого доказу ¬ ψ, то робимо висновок, що Φ.
• Універсальний доказ (або універсальне похідне) - це упорядкований список речень, в якому кожне речення є або передумовою, або походить від попередніх рядків (не в межах завершеного піддоказу) з використанням правила висновку. Якщо ми можемо довести Φ (x ′), де x ′ не з'являється вільним у жодному рядку над універсальною похідною, то робимо висновок, що x Φ (x).

• Схематична форма методів прямого, умовного та непрямого доказу залишається такою ж, як і для логіки пропозиції. Ми можемо використовувати смуги Fitch, щоб виписати цю четверту схему доказів наступним чином:

\ [\ fitchctx {\ коробковий підзахисний [] {\ альфа '} {} {\ еліпси лінії\\\ plline {\ phi (\ альфа')}}\ pline {\ lall\ alpha\ phi (\ альфа)}\]» клас = «ql-img-відображується-рівняння швидкого латексного автоматичного формату» висота = «142" назва = «Відображено QuickLatex .com» ширина = «71" src=» https://human.libretexts.org/@api/deki/files/155767/ Зображення/Швидкий латекс.com-A42FC18DD775 Дие 41Ф61Ф76123CBCD1_L3.PNG» />

• Речення, яке ми можемо довести без передумов, - це теорема.

16.5 Деякі поради щодо перекладів з використанням квантифікаторів

Більшість фраз англійською мовою, які ми хочемо перевести в нашу логіку першого порядку, мають такі форми.

Все Φ х Φ (х)	Щось є Φ х Φ (х)
Ніщо не є Φ ¬х Φ (х)	Щось не Φ х ¬ Φ (х)
Всі Φ є ψ х (Φ (x) → ψ (х))	Деякі Φ становлять х (Φ (х) ^ ψ (х))
Ні Φ є ψ ¬х (Φ (х) ^ ψ (х))	Деякі Φ не є ψ х (Φ (х) ^ ¬ ψ (х))
Тільки Φ - це ψ х (ψ (x) → Φ (х))	Всі і тільки Φ - це ψ х (Φ (x) ↔ ψ (х))