【离散数学 用推理规则证明】前提: p∨q, p->s, q->r 结论: s∨r

Question

构造性二难的证明

Answer 1

┐s∧┐r1置换。┐s2化简。p→s前提引入。┐p34拒取式。┐r2化简。q→r前提引入。┐q67拒取式。┐p∧┐q58合取。因为(┐(p∨q))∧(p∨q)<=>0，所以原推理是正确的。

内容涉及：

1、集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数。

2、图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用。

3、代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数。

4、组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理。

Answer 2

用反证法也就是归谬法。

1 ┐(s∨r) 否定前提引入
2 ┐s∧┐r 1置换
3 ┐s 2化简
4 p→s 前提引入
5 ┐p 34拒取式
6 ┐r 2化简
7 q→r 前提引入
8 ┐q 67拒取式
9 ┐p∧┐q 58合取
10 ┐(p∨q) 9置换
11 p∨q 前提引入
12 (┐(p∨q))∧(p∨q) 11,12合取
因为 (┐(p∨q))∧(p∨q)<=>0，所以原推理是正确的。

－－－－
推理规则术语参考自《离散数学》耿素云 屈婉玲

Answer 3

　　证明1：
　　1）┐s 附加前提引入
　　2）p→s 前提引入
　　3）┐p 1）3）拒取式
　　4）p∨q 前提引入
　　5）q 3）4）析取三段式
　　6）q→r 前提引入
　　7）r 5）6）假言推理
由1）7）得知┐s→r ，即证得s∨r。

　　证明2：
　　1）p→s 前提引入
　　2）q→r 前提引入
　　3）p∨q 前提引入
　　4）s∨r 1）2）3）构造性二难式
即证得。