Teiginių logika ir įrodymai: uždaviniai su sprendimais žingsnis po žingsnio
Nemokami uždaviniai tema Teiginių logika ir įrodymai su brėžiniais, užuominomis ir išsamiais sprendimais. Kiekvieną kartą naujos reikšmės, trijų lygių: teisingumo lentelės, ekvivalentumai ir įrodymo metodai, kvantoriai ir argumentai.
Nemokamas pratybų uždavinysLengvas
Užpildykite teisingumo lentelę (1 = teisinga, 0 = klaidinga). Kiek eilučių N yra teisinga (p → r) ↔ (r ∨ q)?
(p → r) ↔ (r ∨ q)
Tikslus atsakymas: sveikasis skaičius, be apvalinimo.
Kaip spręsti uždavinius tema Teiginių logika ir įrodymai
Suskaičiuokite skirtingus kintamuosius: teisingumo lentelėje yra 2ⁿ eilučių, o pirmoji eilutė – visi kintamieji lygūs 1.
Kiekvienai posakio daliai skirkite savo stulpelį ir užpildykite stulpelius iš vidaus į išorę.
Taikykite kiekvienos jungties taisyklę: → yra 0 tik tada, kai 1 → 0, o ↔ yra 1, kai abi pusės sutampa.
Tikrindami ekvivalentumą, palyginkite galutinius stulpelius eilutė po eilutės; tikrindami argumentą, žiūrėkite tik į eilutes, kuriose visos prielaidos lygios 1.
Norėdami paneigti kvantorių turintį teiginį, perkelkite ¬ į vidų, sukeiskite ∀ ir ∃ vietomis ir paneikite vidinę formulę.
Dažnos klaidos
Laikyti p → q klaidingu, kai p klaidingas.
Kartojamą kintamąjį skaičiuoti du kartus ieškant eilučių skaičiaus.
Painioti kontrapoziciją ¬q → ¬p su atvirkštiniu teiginiu q → p.
Neigti ∀x P(x) kaip ∀x ¬P(x), o ne ∃x ¬P(x).
Taikyti De Morgano dėsnį nesukeitus ∧ ir ∨ vietomis.
Teiginys yra sakinys, kuris yra arba teisingas, arba klaidingas, pavyzdžiui, „7 yra pirminis“. Žymime jį raide p arba q, o jo teisingumo reikšmę – 1 (teisingas) arba 0 (klaidingas).
Jungtys iš mažesnių formulių sudaro didesnes:
¬p (ne p) apverčia reikšmę.
p ∧ q (ir) yra 1 tik tada, kai abu lygūs 1.
p ∨ q (arba) yra 0 tik tada, kai abu lygūs 0. Tai įtraukiantis „arba“: abu gali būti teisingi.
p → q (jei p, tai q) yra 0 tik tada, kai p = 1 ir q = 0.
p ↔ q (tada ir tik tada) yra 1, kai p ir q turi tą pačią reikšmę.
Implikacija daugelį studentų stebina: kai p klaidingas, p → q yra teisingas, kad ir koks būtų q. Pažadas „jei lyja, imu skėtį“ pažeidžiamas tik lietingą dieną be skėčio.
Savikontrolė p = 0 ir q = 1. Kokia p → q reikšmė?
0
1
Neapibrėžta
Priklauso nuo konteksto
Atsakymas: 1. Implikacija klaidinga tik tada, kai sąlyga įvykdyta, o išvada ne (p = 1, q = 0). Kai p = 0, ji teisinga, kad ir koks būtų q.
2Teisingumo lentelės
Teisingumo lentelėje išvardytas kiekvienas kintamųjų teisingumo reikšmių derinys. Kai kintamųjų n skirtingų, yra 2ⁿ eilučių: 4 dviem kintamiesiems, 8 trims, 16 keturiems. Du kartus pasirodantis kintamasis vis tiek skaičiuojamas vieną kartą.
Dirbkite iš vidaus į išorę. Kiekvienai posakio daliai skirkite savo stulpelį, kad kiekvienam naujam stulpeliui reikėtų pritaikyti tik vieną jungtį jau turimiems stulpeliams.
Išvardykite kintamuosius ir užrašykite visus 2ⁿ derinių, pradėdami nuo visų vienetų.
Pridėkite stulpelį kiekvienai posakio daliai, pradėdami nuo giliausios.
Užpildykite kiekvieną stulpelį pagal jo pagrindinės jungties taisyklę.
Atsakymą perskaitykite iš paskutinio stulpelio: suskaičiuokite vienetus arba raskite prašomą eilutę.
Savikontrolė Kiek eilučių turi (p ∧ q) → (r ∨ p) teisingumo lentelė?
16
4
6
8
Atsakymas: 8. Formulėje yra trys skirtingi kintamieji p, q ir r, todėl yra 2³ = 8 eilutės. p pasirodo du kartus, bet tai vienas kintamasis; 16 būtų 2⁴ keturiems pasirodymams.
3Išspręstas pavyzdys
Sekite kiekvieną žingsnį. Pabandykite nuspėti kitą, prieš jį atidarydami.
Išspręstas pavyzdys
Kiek (p → q) ∧ ¬q teisingumo lentelės eilučių yra teisingos?
1
Kintamieji ir eilutės
Du kintamieji p ir q, todėl 4 eilutės: (1, 1), (1, 0), (0, 1), (0, 0).
2
Stulpelis p → q
Jis lygus 0 tik eilutėje p = 1, q = 0:
p → q: 1, 0, 1, 1
3
Stulpelis ¬q
¬q: 0, 1, 0, 1
4
Konjunkcija
Abu stulpeliai turi būti 1. Taip nutinka tik paskutinėje eilutėje, kai p = 0 ir q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Atsakymas
Formulė teisinga 1 eilutėje, kai p = 0, q = 0. Todėl p → q ir ¬q kartu duoda ¬p (modus tollens).
4Ekvivalentumai ir įrodymo metodai
Dvi formulės yra ekvivalenčios (≡), kai jų teisingumo lentelių stulpeliai sutampa. Tautologija yra 1 kiekvienoje eilutėje, prieštara – 0 kiekvienoje eilutėje, o kontingencija nėra nei viena, nei kita.
Dažniausiai naudojami dėsniai:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Šie dėsniai yra įrodymo metodų pagrindas. Kontrapozicijos įrodymas p → q įrodo vietoj jo ¬q → ¬p, kuris yra ekvivalentus. Prieštaros įrodymas daro prielaidą p ∧ ¬q – vienintelį būdą, kaip implikacija gali būti klaidinga, – ir išveda kažką neįmanomo.
Atkreipkite dėmesį: atvirkštinis teiginys q → p ir atvirkštinis neigiamas ¬p → ¬q nėra ekvivalentūs p → q.
Savikontrolė Kuri formulė ekvivalenti ¬(p ∧ q)?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Atsakymas: ¬p ∨ ¬q. Pagal De Morgano dėsnį ∧ tampa ∨ ir abi dalys paneigiamos. ¬p ∧ ¬q yra p ∨ q neigimas, kitas teiginys: jis klaidingas, kai lygiai vienas iš p ir q teisingas, o ¬(p ∧ q) tada teisingas.
5Kvantoriai ir teisingi argumentai
Kai kintamieji kinta srityje, ∀x P(x) sako „P galioja kiekvienam x“, o ∃x P(x) – „P galioja bent vienam x“. Neigimas sukeičia kvantorių:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Perkelkite neigimą į vidų po vieną žingsnį; viduje naudokite teiginių logikos dėsnius. Pavyzdžiui, ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): „ne kiekvienas P yra Q“ reiškia „kai kuris P nėra Q“.
Argumentas yra teisingas (galiojantis), kai išvada lygi 1 kiekvienoje eilutėje, kurioje visos prielaidos lygios 1. Klasikinės galiojančios formos yra modus ponens (p → q, p, taigi q), modus tollens (p → q, ¬q, taigi ¬p) ir hipotetinis silogizmas (p → q, q → r, taigi p → r).
Eilutė, kurioje visos prielaidos lygios 1, o išvada 0, yra kontrapavyzdys. Pasekmės patvirtinimas (p → q, q, taigi p) negalioja: eilutė p = 0, q = 1 yra kontrapavyzdys.
Savikontrolė Koks yra teiginio „visi studentai išlaikė“, ∀x P(x), neigimas?
¬P(x) vienam pasirinktam studentui x
∀x ¬P(x): niekas neišlaikė
∃x P(x): kai kurie studentai išlaikė
∃x ¬P(x): kai kurie studentai neišlaikė
Atsakymas: ∃x ¬P(x): kai kurie studentai neišlaikė. Vieno neišlaikiusio studento pakanka, kad „visi studentai išlaikė“ būtų klaidingas. „Niekas neišlaikė“ yra daug stipresnis už neigimą.
6Dažnos klaidos
Laikyti p → q klaidingu, kai p klaidingas. Jis klaidingas tik kai p = 1 ir q = 0.
Kartojamą kintamąjį skaičiuoti du kartus ieškant eilučių skaičiaus.
Painioti kontrapoziciją ¬q → ¬p su atvirkštiniu teiginiu q → p arba atvirkštiniu neigiamu ¬p → ¬q.
Neigti ∀x P(x) kaip ∀x ¬P(x): kvantorius turi pasikeisti į ∃.
Užrašyti ¬(p ∧ q) kaip ¬p ∧ ¬q: De Morgano dėsnis taip pat sukeičia jungtį.
Savikontrolė Kuris teiginys yra teiginio „jei n² lyginis, tai n lyginis“ kontrapozicija?
Jei n lyginis, tai n² lyginis
Jei n nelyginis, tai n² nelyginis
Jei n² nelyginis, tai n nelyginis
n² lyginis, o n nelyginis
Atsakymas: Jei n nelyginis, tai n² nelyginis. Sukeiskite abi dalis ir paneikite jas: ne (n lyginis) → ne (n² lyginis). „Jei n lyginis, tai n² lyginis“ yra atvirkštinis teiginys; paskutinis variantas yra tai, ką daro prielaida įrodant prieštara.
7Kaip atrodo egzamino uždaviniai
Lengvas: teisingumo lentelės. Randate eilučių skaičių, skaičiuojate eilutes, kuriose formulė teisinga, arba pasirenkate vienintelę eilutę, dėl kurios formulė teisinga ar klaidinga.
Vidutinis: ekvivalentumai ir įrodymo metodai. Nusprendžiate, ar formulė yra tautologija, prieštara ar kontingencija, pasirenkate ekvivalenčią formulę arba teiginį, kurį reikia įrodyti kontrapozicija ar prieštara.
Sunkus: kvantoriai ir argumentai. Neigiate kvantorių turinčius teiginius, pasirenkate iš prielaidų išplaukiančią išvadą, pasirenkate negaliojančio argumento kontrapavyzdžio eilutę arba skaičiuojate teisingas keturių kintamųjų lentelės eilutes.
Lygiai viena teisingumo lentelės eilutė daro ¬(p ∨ q) → q klaidingą. Spustelėkite tą eilutę.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Rodyti užuominas
a → b yra 0 tik tada, kai a = 1 ir b = 0. ¬a apverčia reikšmę. a ∨ b yra 0 tik tada, kai abu lygūs 0.
Pirmiausia išnagrinėkite pagrindinę jungtį: kokios turi būti jos abi pusės, kad visa formulė būtų 0?
Kiekvienai daliai skirkite savo stulpelį: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Rodyti atsakymą ir paaiškinimą
Teisingumo lentelės: formulė su n skirtingų kintamųjų turi 2ⁿ eilučių, po vieną kiekvienam teisingumo reikšmių deriniui (1 = teisinga, 0 = klaidinga). Dirbkite iš vidaus į išorę ir kiekvienai posakio daliai skirkite savo stulpelį. ¬a apverčia reikšmę; a ∧ b yra 1 tik tada, kai abu lygūs 1; a ∨ b yra 0 tik tada, kai abu lygūs 0; a → b yra 0 tik tada, kai a = 1 ir b = 0; a ↔ b yra 1, kai abi pusės lygios.
Kuri formulė yra logiškai ekvivalenti (b ∧ c) → a? Spustelėkite ją.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Rodyti užuominas
Ekvivalenčios formulės sutampa kiekvienoje teisingumo lentelės eilutėje. Viena eilutė, kurioje jos skiriasi, atmeta variantą.
Išbandykite eilutę, kuri (b ∧ c) → a daro 0, ir patikrinkite, kurie variantai joje taip pat lygūs 0.
Eksportacija: (a ∧ b) → c ≡ a → (b → c). Abi yra 0 tik tada, kai a = 1, b = 1 ir c = 0.
Rodyti atsakymą ir paaiškinimą
Loginis ekvivalentumas: dvi formulės yra ekvivalenčios (≡), kai kiekvienoje teisingumo lentelės eilutėje turi tą pačią reikšmę. Tautologija yra 1 kiekvienoje eilutėje, prieštara – 0 kiekvienoje eilutėje, o kontingencija nėra nei viena, nei kita. Naudingi dėsniai: De Morgano, ¬(a ∧ b) ≡ ¬a ∨ ¬b ir ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (kontrapozicija); ¬(a → b) ≡ a ∧ ¬b; ir distributyvumo dėsniai, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Dėsnis
Eksportacija: (a ∧ b) → c ≡ a → (b → c). Abi yra 0 tik tada, kai a = 1, b = 1 ir c = 0.
(b ∧ c) → a ≡ b → (c → a)
Patikrinkite teisingumo lentele
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Atsakymas
b → (c → a)
Stulpeliai po brūkšniu yra variantai pateikta tvarka.
Pavyzdys 3Sunkus
Duotos prielaidos (q ∧ p) → r; q; ¬r. Kokia išvada iš jų išplaukia? Spustelėkite ją.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Rodyti užuominas
Išvada išplaukia, kai ji lygi 1 kiekvienoje eilutėje, kurioje visos prielaidos lygios 1.
Raskite eilutes, kuriose visos prielaidos lygios 1, ir išbandykite kiekvieną variantą tose eilutėse.
Tai standartinė taisyklė: modus tollens su konjunkcija.
Rodyti atsakymą ir paaiškinimą
Kvantoriai ir argumentai: ¬∀x P(x) ≡ ∃x ¬P(x) ir ¬∃x P(x) ≡ ∀x ¬P(x). Perkelkite neigimą į vidų, sukeiskite kiekvieną kvantorių, pro kurį jis praeina, o vidinę formulę paneikite teiginių logikos dėsniais, pavyzdžiui, ¬(a → b) ≡ a ∧ ¬b. Argumentas yra teisingas (galiojantis), kai išvada lygi 1 kiekvienoje eilutėje, kurioje visos prielaidos lygios 1. Viena eilutė su teisingomis prielaidomis ir klaidinga išvada yra kontrapavyzdys ir rodo, kad argumentas negalioja.
Eilutės, kuriose visos prielaidos teisingos
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Išvada
¬p (modus tollens su konjunkcija)
Atsakymas
¬p
Klausimai ir atsakymai
Teiginių logika ir įrodymai: kas tai?
Jungtys iš mažesnių formulių sudaro didesnes:
Implikacija daugelį studentų stebina: kai p klaidingas, p → q yra teisingas, kad ir koks būtų q. Pažadas „jei lyja, imu skėtį“ pažeidžiamas tik lietingą dieną be skėčio.
Teiginių logika ir įrodymai: kaip spręsti uždavinius žingsnis po žingsnio?
Suskaičiuokite skirtingus kintamuosius: teisingumo lentelėje yra 2ⁿ eilučių, o pirmoji eilutė – visi kintamieji lygūs 1.
Kiekvienai posakio daliai skirkite savo stulpelį ir užpildykite stulpelius iš vidaus į išorę.
Taikykite kiekvienos jungties taisyklę: → yra 0 tik tada, kai 1 → 0, o ↔ yra 1, kai abi pusės sutampa.
Tikrindami ekvivalentumą, palyginkite galutinius stulpelius eilutė po eilutės; tikrindami argumentą, žiūrėkite tik į eilutes, kuriose visos prielaidos lygios 1.
Norėdami paneigti kvantorių turintį teiginį, perkelkite ¬ į vidų, sukeiskite ∀ ir ∃ vietomis ir paneikite vidinę formulę.
Teiginių logika ir įrodymai: kokios klaidos dažniausios?
Laikyti p → q klaidingu, kai p klaidingas.
Kartojamą kintamąjį skaičiuoti du kartus ieškant eilučių skaičiaus.
Painioti kontrapoziciją ¬q → ¬p su atvirkštiniu teiginiu q → p.
Neigti ∀x P(x) kaip ∀x ¬P(x), o ne ∃x ¬P(x).
Taikyti De Morgano dėsnį nesukeitus ∧ ir ∨ vietomis.
Teiginių logika ir įrodymai: ką lavinsite?
Lengvas: teisingumo lentelės
Vidutinis: ekvivalentumai ir įrodymo metodai
Sunkus: kvantoriai ir argumentai
Kiekviename uždavinyje naujos reikšmės, todėl išmokstate metodą, o ne atsakymą. Strigote? Pirmiausia atverkite nedidelę užuominą, o visą paaiškinimą – tik kai jo prireiks.
Kaip vyksta praktika
Kiekviename uždavinyje naujos reikšmės, todėl išmokstate metodą, o ne atsakymą.
Strigote? Pirmiausia atverkite nedidelę užuominą, o visą paaiškinimą – tik kai jo prireiks.
Jūsų pažanga, klaidos ir išsaugoti uždaviniai išlieka, todėl prieš egzaminą galite viską pakartoti.