Formuła logiczna

W logice mówimy o skończonej serii listów, że jest to formuła , a czasem dobrze uformowane formuła , o danej logicznej języka , gdy może ona być wykonana przy zastosowaniu kombinacji zasad związanej formalnej gramatyki , mówimy o składnia języka. Nieformalnie formuły to zbiory liter, którym można nadać znaczenie w kategoriach wartości prawdy (prawda lub fałsz). Formuły logiczne są odpowiednikiem zdań w języku naturalnym.

Formuły językowe interpretuje się zgodnie z semantyką rozważanej logiki, przypisując im wartość prawdziwości . Składnia obliczania predykatów wymaga wprowadzenia innego pojęcia, pojęcia terminu , składni terminów języka połączonego z sygnaturą . Terminy są interpretowane przez obiekty (liczby, punkty itp.).

Możliwe jest zestawianie wzorów do budowania dowodów , zgodnie z formalnymi regułami związanymi z systemem dedukcji .

Nazwa „dobrze sformułowana formuła” (tłumaczenie (en) dobrze sformułowana formuła ) na formułę jest śladem dawnego użycia, w którym formuły nazywaliśmy skończonymi sekwencjami dowolnych znaków.

Wprowadzenie

Kluczowym zastosowaniem formuł jest logika zdań , na przykład logika pierwszego rzędu . W tym kontekście formuła jest ciągiem symboli φ, dla których musimy zadać sobie pytanie „czy φ prawda?”, Kiedy wszystkie wolne zmienne w φ zostaną utworzone. W logice formalnej dowody można przedstawić za pomocą szeregu formuł o określonych właściwościach, a ostateczna formuła jest tym, co zostało udowodnione.

Formuły to obiekty składniowe. Są podane przez interpretacje. Na przykład w formule zdaniowej każda zmienna zdaniowa może być interpretowana jako zdanie konkretne, tak że ogólna formuła wyraża związek między tymi zdaniami.

Obliczanie ofert

Formuły wynikające z obliczenia zdań , zwane także formułami zdaniowymi, są wyrażeniami formy . Ich definicja rozpoczyna się od arbitralnego wyboru wyznaczonej V o zmiennych zdaniowych . Alfabet składa się z litery V z odpowiednimi symbolami w koniunkcji oraz propozycjonalnych nawiasach „(” i „)”, które nie powinny być V . Formuły będą określonymi wyrażeniami (czyli ciągami symboli) w tym alfabecie. Wzory są indukcyjnie zdefiniowane w następujący sposób: W∧(b∧VS){\ Displaystyle A \ ziemia (B \ ziemia C)}

• Każda zmienna zdaniowa sama w sobie jest formułą.
• Jeśli φ jest formułą, to  φ jest formułą.¬{\ displaystyle \ lnot}
• Jeśli φ i ψ są formułami, a • jest dowolnym łącznikiem binarnym, to (φ • ψ) jest formułą. Tutaj • może być (ale nie tylko) jeden ze zwykłych operatorów ∨, ∧, → lub ↔. Definicję tę można również zapisać w gramatyce formalnej jako Backus-Naur , pod warunkiem, że zestaw zmiennych jest zakończony:

  <zestaw alfa> :: = p | q | r | s | t | u | ... (dowolny skończony zbiór zmiennych zdaniowych)

  <form> :: = <zestaw alfa> | <form> | (<form> <form>) | (<form> <form>) | (<form> <form>) | (<form> <form>)¬{\ displaystyle \ neg}∧{\ displaystyle \ wedge}∨{\ displaystyle \ vee}→{\ displaystyle \ rightarrow}↔{\ displaystyle \ leftrightarrow}

Używając tej gramatyki, sekwencja symboli

(( p q ) ( r s )) ( q s )) jest formułą, ponieważ jest poprawna gramatycznie. Seria symboli→{\ displaystyle \ rightarrow} ∧{\ displaystyle \ wedge} →{\ displaystyle \ rightarrow} ∨{\ displaystyle \ vee}¬{\ displaystyle \ neg} ∧{\ displaystyle \ wedge} ¬{\ displaystyle \ neg} (( p q ) ( qq )) p ))→{\ displaystyle \ rightarrow} →{\ displaystyle \ rightarrow}

nie jest formułą, ponieważ nie jest zgodna z gramatyką.

Złożony wzór może być trudny do odczytania, na przykład z powodu mnożenia nawiasów. Aby rozwiązać ten problem, między operatorami nakładane są reguły pierwszeństwa (podobne do standardowej matematycznej kolejności operacji ), co sprawia, że ​​niektóre operatory są bardziej restrykcyjne niż inne. Na przykład przy założeniu, że priorytet (najbardziej ograniczający, a przynajmniej wiążący) 1.   2.   3.   4 .. Tak więc formuła ¬{\ displaystyle \ neg}→{\ displaystyle \ rightarrow}∧{\ displaystyle \ wedge}∨{\ displaystyle \ vee}

(( p q ) ( r s )) ( q s )) można skrócić→{\ displaystyle \ rightarrow} ∧{\ displaystyle \ wedge} →{\ displaystyle \ rightarrow} ∨{\ displaystyle \ vee}¬{\ displaystyle \ neg} ∧{\ displaystyle \ wedge} ¬{\ displaystyle \ neg} p q r s q s→{\ displaystyle \ rightarrow} ∧{\ displaystyle \ wedge} →{\ displaystyle \ rightarrow} ∨{\ displaystyle \ vee} ¬{\ displaystyle \ neg} ∧{\ displaystyle \ wedge} ¬{\ displaystyle \ neg}

Jest to jednak tylko konwencja stosowana w celu uproszczenia przedstawienia pisemnej formuły.

Logika predykatów

Definicja formuły w logice pierwszego rzędu jest związana z jej sygnaturą danej teorii. Podpis ten określa stałe, relacyjne i funkcyjne symbole teorii, a także arcydzieła funkcji i symboli relacji. QS{\ displaystyle {\ mathcal {QS}}}

Definicja wzoru składa się z kilku części. Po pierwsze, zestaw terminów jest definiowany rekurencyjnie. Terminy, nieformalnie, są wyrażeniami, które reprezentują przedmioty w dziedzinie dyskursu .

1. Każda zmienna jest terminem.
2. Każdy stały symbol podpisu jest terminem
3. wyrażenie postaci f ( t 1 , ..., t n ), gdzie f jest symbolem funkcji n -arnej, a t 1 , ..., t n są wyrazami, nadal jest terminem.

Następnym krokiem jest zdefiniowanie wzorów atomowych .

1. Jeżeli T 1 i T 2 są warunki, to T 1 = T 2 jest wzór atomowej.
2. Jeśli R jest symbolem relacji n -arnej, a t 1 , ..., t n są terminami, to R ( t 1 , ..., t n ) jest formułą atomową.

Wreszcie zbiór formuł jest zdefiniowany jako najmniejszy zbiór zawierający zbiór formuł atomowych, takich jak:

1. ¬ϕ{\ displaystyle \ neg \ phi}jest formułą, kiedy jest formułą ϕ{\ displaystyle \ \ phi}
2. (ϕ∧ψ){\ Displaystyle (\ phi \ land \ psi)}i są formułami, kiedy i są formułami;(ϕ∨ψ){\ Displaystyle (\ phi \ lor \ psi)} ϕ{\ displaystyle \ \ phi} ψ{\ displaystyle \ \ psi}
3. ∃xϕ{\ Displaystyle \ istnieje x \, \ phi}jest formułą, gdy jest zmienną i jest formułą; x{\ displaystyle \ x} ϕ{\ displaystyle \ \ phi}
4. ∀xϕ{\ displaystyle \ forall x \, \ phi}jest formułą, gdy jest zmienną i jest formułą (alternatywnie można ją zdefiniować jako skrót ). x{\ displaystyle \ x} ϕ{\ displaystyle \ \ phi}∀xϕ{\ displaystyle \ forall x \, \ phi}¬∃x¬ϕ{\ Displaystyle \ neg \ istnieje x \, \ neg \ phi}

Jeśli formuła nie występuje lub , dla żadnej zmiennej , jest wywoływana bez kwantyfikatora . Egzystencjalny wzór składa się z szeregu ilościowego egzystencjalnych następnie formule bez kwantyfikatora. ∃x{\ Displaystyle \ istnieje x}∀x{\ displaystyle \ forall x} x{\ displaystyle \ x}

Formuły otwarte i atomowe

Formuła atomowa jest formułą, która nie zawiera złącza logicznych lub kwantyfikatorów . Dokładna forma formuł atomowych zależy od danego systemu formalnego ; na przykład dla logiki zdań formuły atomowe są zmiennymi zdaniowymi . Do obliczania predykatów formuły atomowe są symbolami predykatów z ich argumentami, przy czym każdy argument jest terminem.

Zgodnie z terminologią formuła otwarta jest tworzona przez łączenie formuł atomowych przy użyciu tylko łączników logicznych, z wyłączeniem kwantyfikatorów. Nie należy go mylić z formułą, która nie jest zamknięta.

Właściwości mające zastosowanie do wzorów

• Formuła w języku jest ważny , jeśli jest prawdziwa dla dowolnej interpretacji z dnia .Q{\ displaystyle {\ mathcal {Q}}}Q{\ displaystyle {\ mathcal {Q}}}
• Formuła w języku jest zadowalająca , jeśli prawdą jest, dla niektórych interpretacji z .Q{\ displaystyle {\ mathcal {Q}}}Q{\ displaystyle {\ mathcal {Q}}}
• Formuła A w języku arytmetyki jest rozstrzygalna, jeśli reprezentuje zbiór rozstrzygalny , a mianowicie, jeśli istnieje skuteczna metoda, która przy podstawieniu wolnych zmiennych A mówi, czy A jest dające się udowodnić, czy też jego negacja l 'jest.

Bibliografia

• (fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu w angielskiej Wikipedii zatytułowanego „  Dobrze uformowane forumla  ” ( zobacz listę autorów ) .

1. Logika pierwszego rzędu i automatyczne dowodzenie twierdzeń, Melvin Fitting, Springer, 1996 [1]
2. Handbook of the history of logic, (tom 5, Logic from Russell to Church), logika Tarskiego autorstwa Keitha Simmonsa, D. Gabbaya i J. Woodsa Edsa, str. 568 [2] .

Zobacz też

• Formuła (logika matematyczna)
• Formuła zdaniowa
• Normalne formy łączące i normalne formy rozłączne
• Logika , logika wektor , intuicjonistycznej logika , minimal logika , logika liniowy , nieskończonej logika
• Sylogizm
• Ideografia
• Rachunek lambda
• Logiki wielowartościowe
• Logika opisu

Bibliografia

• René Cori, Daniel Lascar, Logika matematyczna, tom 1: Rachunek zdań, algebra Boole'a, rachunek predykatów [ szczegóły wydań ]

Linki zewnętrzne

• Terminologia i ontologia - Cairn.info
• Semantyka zdań
• Natura teorii naukowych
• (en) Dobrze sformułowana formuła logiki predykatów pierwszego rzędu - zawiera krótki test w Javie .
• (en) Dobrze sformułowana formuła w ProvenMath

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">