Matematyka dyskretna - logika zdań
Reguły logiki matematycznej określają metody wnioskowania twierdzeń matematycznych. Grecki filozof Arystoteles był pionierem logicznego rozumowania. Logiczne rozumowanie stanowi podstawę teoretyczną dla wielu dziedzin matematyki, a co za tym idzie informatyki. Ma wiele praktycznych zastosowań w informatyce, takich jak projektowanie maszyn obliczeniowych, sztuczna inteligencja, definiowanie struktur danych dla języków programowania itp.
Propositional Logicdotyczy stwierdzeń, którym można przypisać wartości prawdy, „prawda” i „fałsz”. Celem jest przeanalizowanie tych stwierdzeń indywidualnie lub w sposób złożony.
Logika przyimkowa - definicja
Zdanie to zbiór zdań deklaratywnych, które mają albo wartość prawdziwości „prawda”, albo wartość prawdy „fałsz”. Zdanie składa się ze zmiennych zdaniowych i łączników. Zmienne zdaniowe oznaczamy dużymi literami (A, B itd.). Łączniki łączą zmienne zdaniowe.
Poniżej podano kilka przykładów twierdzeń -
- „Człowiek jest śmiertelny”, zwraca wartość prawdy „PRAWDA”
- „12 + 9 = 3 - 2”, zwraca wartość prawdy „FALSE”
Poniższe nie jest propozycją -
„A jest mniejsze niż 2”. Dzieje się tak, ponieważ dopóki nie podamy określonej wartości A, nie możemy powiedzieć, czy stwierdzenie jest prawdziwe czy fałszywe.
Połączenia
W logice zdań generalnie używamy pięciu połączeń, które są -
LUB ($ \ lor $)
AND ($ \ land $)
Negacja / NIE ($ \ lnot $)
Implikacja / jeśli-to ($ \ rightarrow $)
Jeśli i tylko wtedy, gdy ($ \ Leftrightarrow $).
OR ($\lor$) - Operacja OR dwóch zdań A i B (zapisanych jako $ A \ l lub B $) jest prawdą, jeśli przynajmniej którakolwiek ze zmiennych zdań A lub B jest prawdziwa.
Tabela prawdy jest następująca -
| ZA | b | A ∨ B |
|---|---|---|
| Prawdziwe | Prawdziwe | Prawdziwe |
| Prawdziwe | Fałszywy | Prawdziwe |
| Fałszywy | Prawdziwe | Prawdziwe |
| Fałszywy | Fałszywy | Fałszywy |
AND ($\land$) - Operacja AND dwóch zdań A i B (zapisanych jako $ A \ land B $) jest prawdą, jeśli obie zmienne zdań A i B są prawdziwe.
Tabela prawdy jest następująca -
| ZA | b | A ∧ B |
|---|---|---|
| Prawdziwe | Prawdziwe | Prawdziwe |
| Prawdziwe | Fałszywy | Fałszywy |
| Fałszywy | Prawdziwe | Fałszywy |
| Fałszywy | Fałszywy | Fałszywy |
Negation ($\lnot$) - Negacja zdania A (zapisanego jako $ \ lnot A $) jest fałszem, gdy A jest prawdą, i jest prawdziwą, gdy A jest fałszem.
Tabela prawdy jest następująca -
| ZA | ¬ A |
|---|---|
| Prawdziwe | Fałszywy |
| Fałszywy | Prawdziwe |
Implication / if-then ($\rightarrow$)- Implikacją $ A \ rightarrow B $ jest zdanie „jeśli A, to B”. Jest fałszem, jeśli A jest prawdą, a B jest fałszem. Pozostałe przypadki są prawdziwe.
Tabela prawdy jest następująca -
| ZA | b | A → B |
|---|---|---|
| Prawdziwe | Prawdziwe | Prawdziwe |
| Prawdziwe | Fałszywy | Fałszywy |
| Fałszywy | Prawdziwe | Prawdziwe |
| Fałszywy | Fałszywy | Prawdziwe |
If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ jest dwuwarunkowym łącznikiem logicznym, który jest prawdą, gdy p i q są takie same, tj. Oba są fałszywe lub oba są prawdziwe.
Tabela prawdy jest następująca -
| ZA | b | A ⇔ B |
|---|---|---|
| Prawdziwe | Prawdziwe | Prawdziwe |
| Prawdziwe | Fałszywy | Fałszywy |
| Fałszywy | Prawdziwe | Fałszywy |
| Fałszywy | Fałszywy | Prawdziwe |
Tautologie
Tautologia to formuła, która jest zawsze prawdziwa dla każdej wartości jej zmiennych zdaniowych.
Example - Udowodnij, że $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ jest tautologią
Tabela prawdy jest następująca -
| ZA | b | A → B | (A → B) ∧ A | [(A → B) ∧ A] → B |
|---|---|---|---|---|
| Prawdziwe | Prawdziwe | Prawdziwe | Prawdziwe | Prawdziwe |
| Prawdziwe | Fałszywy | Fałszywy | Fałszywy | Prawdziwe |
| Fałszywy | Prawdziwe | Prawdziwe | Fałszywy | Prawdziwe |
| Fałszywy | Fałszywy | Prawdziwe | Fałszywy | Prawdziwe |
Jak widzimy, każda wartość $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ jest „True”, jest to tautologia.
Sprzeczności
Sprzeczność to formuła, która zawsze jest fałszywa dla każdej wartości jej zmiennych zdaniowych.
Example - Udowodnij, że $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ jest sprzecznością
Tabela prawdy jest następująca -
| ZA | b | A ∨ B | ¬ A | ¬ B. | (¬ A) ∧ (¬ B) | (A ∨ B) ∧ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Prawdziwe | Prawdziwe | Prawdziwe | Fałszywy | Fałszywy | Fałszywy | Fałszywy |
| Prawdziwe | Fałszywy | Prawdziwe | Fałszywy | Prawdziwe | Fałszywy | Fałszywy |
| Fałszywy | Prawdziwe | Prawdziwe | Prawdziwe | Fałszywy | Fałszywy | Fałszywy |
| Fałszywy | Fałszywy | Fałszywy | Prawdziwe | Prawdziwe | Prawdziwe | Fałszywy |
Jak widzimy, każda wartość $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ to „Fałsz”, jest to sprzeczność.
Przypadkowość
Zależność jest formułą, która ma zarówno pewne wartości prawdziwe, jak i pewne fałszywe dla każdej wartości swoich zmiennych propozycyjnych.
Example - Udowodnij, że $ (A \ lor B) \ land (\ lnot A) $ jest przypadkiem
Tabela prawdy jest następująca -
| ZA | b | A ∨ B | ¬ A | (A ∨ B) ∧ (¬ A) |
|---|---|---|---|---|
| Prawdziwe | Prawdziwe | Prawdziwe | Fałszywy | Fałszywy |
| Prawdziwe | Fałszywy | Prawdziwe | Fałszywy | Fałszywy |
| Fałszywy | Prawdziwe | Prawdziwe | Prawdziwe | Prawdziwe |
| Fałszywy | Fałszywy | Fałszywy | Prawdziwe | Fałszywy |
Jak widzimy, każda wartość $ (A \ lor B) \ land (\ lnot A) $ ma zarówno „Prawda”, jak i „Fałsz”, jest to przypadek.
Równoważności zdań
Dwie instrukcje X i Y są logicznie równoważne, jeśli zachodzi którykolwiek z poniższych dwóch warunków -
Tabele prawdy każdego stwierdzenia mają te same wartości prawdy.
Instrukcja dwuwarunkowa $ X \ Leftrightarrow Y $ jest tautologią.
Example - Udowodnij, że $ \ lnot (A \ lor B) i \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ są równoważne
Testowanie pierwszą metodą (pasująca tabela prawdy)
| ZA | b | A ∨ B | ¬ (A ∨ B) | ¬ A | ¬ B. | [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Prawdziwe | Prawdziwe | Prawdziwe | Fałszywy | Fałszywy | Fałszywy | Fałszywy |
| Prawdziwe | Fałszywy | Prawdziwe | Fałszywy | Fałszywy | Prawdziwe | Fałszywy |
| Fałszywy | Prawdziwe | Prawdziwe | Fałszywy | Prawdziwe | Fałszywy | Fałszywy |
| Fałszywy | Fałszywy | Fałszywy | Prawdziwe | Prawdziwe | Prawdziwe | Prawdziwe |
Tutaj widzimy, że wartości prawdy $ \ lnot (A \ lor B) i \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ są takie same, stąd stwierdzenia są równoważne.
Testowanie przy 2 -go metodą (Bi uwarunkowania)
| ZA | b | ¬ (A ∨ B) | [(¬ A) ∧ (¬ B)] | [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|
| Prawdziwe | Prawdziwe | Fałszywy | Fałszywy | Prawdziwe |
| Prawdziwe | Fałszywy | Fałszywy | Fałszywy | Prawdziwe |
| Fałszywy | Prawdziwe | Fałszywy | Fałszywy | Prawdziwe |
| Fałszywy | Fałszywy | Prawdziwe | Prawdziwe | Prawdziwe |
Ponieważ $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ jest tautologią, instrukcje są równoważne.
Odwrotność, konwersja i przeciwdziałanie dodatnim
Implikacja / jeśli-to $ (\ rightarrow) $ jest również nazywana instrukcją warunkową. Składa się z dwóch części -
- Hipoteza, s
- Wniosek, q
Jak wspomniano wcześniej, jest oznaczony jako $ p \ rightarrow q $.
Example of Conditional Statement- „Jeśli odrobisz pracę domową, nie zostaniesz ukarany”. Tutaj „odrabiasz pracę domową” to hipoteza, p, a „nie zostaniesz ukarany” to konkluzja, q.
Inverse- Odwrotnością zdania warunkowego jest zaprzeczenie zarówno hipotezy, jak i wniosku. Jeśli stwierdzeniem jest „Jeśli p, to q”, odwrotnością będzie „Jeśli nie p, to nie q”. Zatem odwrotnością $ p \ rightarrow q $ jest $ \ lnot p \ rightarrow \ lnot q $.
Example - Odwrotność „Jeśli odrabiasz pracę domową, nie zostaniesz ukarany”, to „Jeśli nie odrabiasz pracy domowej, zostaniesz ukarany”.
Converse- Odwrotność zdania warunkowego jest obliczana poprzez zamianę hipotezy i wniosku. Jeśli stwierdzeniem jest „Jeśli p, to q”, odwrotnością będzie „Jeśli q, to p”. Odwrotność $ p \ rightarrow q $ to $ q \ rightarrow p $.
Example - Odwrotność: „Jeśli odrabiasz pracę domową, nie zostaniesz ukarany”, brzmi: „Jeśli nie zostaniesz ukarany, odrabiasz lekcje”.
Contra-positive- Przeciwwskazanie warunku jest obliczane poprzez zamianę hipotezy i wniosku ze stwierdzenia odwrotnego. Jeśli stwierdzeniem jest „Jeśli p, to q”, wynikiem przeciwstawnym będzie „Jeśli nie q, to nie p”. Przeciwwskazanie $ p \ rightarrow q $ to $ \ lnot q \ rightarrow \ lnot p $.
Example - Przeciwstawne stwierdzenie „Jeśli odrabiasz pracę domową, nie zostaniesz ukarany” to „Jeśli zostaniesz ukarany, nie odrobiłeś pracy domowej”.
Zasada dwoistości
Zasada dwoistości mówi, że dla każdego prawdziwego stwierdzenia, podwójne stwierdzenie uzyskane przez zamianę związków na przecięcia (i odwrotnie) i zamianę zbioru uniwersalnego na zbiór zerowy (i odwrotnie) jest również prawdziwe. Jeśli podwójne w jakimkolwiek stwierdzeniu jest samo stwierdzenie, to jest powiedzianeself-dual komunikat.
Example - Podwójna wartość $ (A \ cap B) \ cup C $ to $ (A \ cup B) \ cap C $
Formy normalne
Możemy przekształcić dowolne zdanie w dwie normalne formy -
- Postać normalna koniunkcyjna
- Rozłączna postać normalna
Koniunkcyjna forma normalna
Zdanie złożone ma postać normalną koniunkcji, jeśli jest otrzymywane przez operację AND między zmiennymi (w tym negacja zmiennych) związanymi z OR. Pod względem operacji na zbiorach jest to instrukcja złożona uzyskana przez Przecięcie między zmiennymi związanymi ze Związkami.
Examples
$ (A \ lor B) \ land (A \ lor C) \ land (B \ lor C \ lor D) $
$ (P \ cup Q) \ cap (Q \ cup R) $
Rozłączna postać normalna
Instrukcja złożona ma rozłączną postać normalną, jeśli jest otrzymywana przez operację LUB pomiędzy zmiennymi (łącznie z negacją zmiennych) związanymi z AND. Pod względem operacji na zbiorach jest to złożona instrukcja uzyskiwana przez Union wśród zmiennych związanych z przecięciami.
Examples
$ (A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D) $
$ (P \ cap Q) \ cup (Q \ cap R) $