第1讲命题逻辑基础 1.命题、命题符号化 2.合式公式、真值表、永真式 3.逻辑等值式、推理定律 4.形式化证明 《集合论与图论》第1讲
《集合论与图论》第1讲 1 第1讲 命题逻辑基础 1. 命题、命题符号化 2. 合式公式、真值表、永真式 3. 逻辑等值式、推理定律 4. 形式化证明
命题符号化 静简单命题:p,qr;p1q1r1 癱联结词 合取联结词:∧ 析取联结词:√ 否定联结词: 蕴涵联结词:→ 等价联结词: 逻辑真值:0,1 《集合论与图论》第1讲
《集合论与图论》第1讲 2 命题符号化 简单命题： p,q,r,p1,q1,r1,… 联结词： 合取联结词：∧ 析取联结词：∨ 否定联结词：¬ 蕴涵联结词：→ 等价联结词：↔ 逻辑真值： 0，1
真值表 truth-table 壽赋值( assignment):给变元指定0、1值 n个变元,共有2种不同的赋值 pq-0p0∧qpvq0->q0>q 00 010 000 00 1101 《集合论与图论》第1讲
《集合论与图论》第1讲 3 真值表(truth-table) 赋值(assignment)：给变元指定0、1值 n个变元，共有2n种不同的赋值 1 1 0 0 ¬p 1 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 p q p∧q p∨q p→q p↔q
真值表(续) p q (pq)→r|-0-qMr 000 001 00 00 《集合论与图论》第1讲
《集合论与图论》第1讲 4 真值表(续) 1 1 1 1 1 1 0 1 ¬p∨¬q∨r 0 1 0 1 0 1 0 1 r 1 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 p q (p∧q)→r
永真式 tautology ●永真式在各种赋值下取值均为真(重言式) 永假式在各种赋值下取值均为假(矛盾式 可满足式:非永假式 pq-(p)-py-g-(×Q)(-p~ 001 1111 10 《集合论与图论》第1讲
《集合论与图论》第1讲 5 永真式(tautology) 永真式:在各种赋值下取值均为真(重言式) 永假式:在各种赋值下取值均为假(矛盾式) 可满足式：非永假式 1 1 1 1 1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 p q ¬(p∧q) ¬p∨¬q ¬(p∧q)↔(¬p∨¬q)