数理逻辑基础

HW1

题目1

image-20230321204224170

(1)

PQPQPQQ¬(PQQ)
00010
01010
10010
11110

该式为永假公式(矛盾式).

(2)

PQRPQP(PQ)PR(P(PQ))(PR)
0000111
0010111
0101111
0111111
1001101
1011111
1101101
1111111

该式为永真公式(重言式).

(3)

PQRPQPR(PQ)(PR)
000001
001001
010100
011100
100100
101111
110100
111111

该式为可满足公式.

题目2

image-20230321205755776

PQ¬QA=PQB=P¬Q¬A¬BAB¬(AB)¬A¬B
0011001100
0101001100
1010110100
1101001100

从而公式 AB 适合德·摩根律

¬(AB)¬A¬B.

题目3

image-20230321210517937

(1)

P(QR)¬P(QR)()¬P(¬QR)()(¬P¬Q)R( )¬(¬P¬Q)R()(PQ)R.(德·摩根定律)

(2)

¬P(¬QR)(¬P¬Q)R( )(1)¬(PQ)R,(·)
(QR)(PR)(QP)R( )(2)(PQ)R.( )

(1)(2)

(¬P(¬QR))(QR)(PR)(¬P(¬QR))((QR)(PR))( )(¬(PQ)R)((PQ)R)((1)(2))(¬(PQ)(PQ))R( )TR()R.()

HW2

题目1

image-20230322145700323

(1)

P(QR)¬P(QR)()¬P(¬QR)()(¬P¬Q)R( )¬(PQ)R(·)¬((PQ)¬R).(·)

(2)

¬(PQ)R¬(¬PQ)R()(P¬Q)R(·)(PR)(¬QR)( )¬(¬((PR)(¬QR)))()¬(¬(PR)¬(¬QR))(·)¬((¬P¬R)(Q¬R)).(·)

(3)

PQ(PQ)(QP)()(¬PQ)(¬QP)()((¬PQ)¬Q)((¬PQ)P)( )((¬P¬Q)(Q¬Q))((¬PP)(QP))( )((¬P¬Q)F)(F(QP))()(¬P¬Q)(QP)()(¬P¬Q)(PQ)( )¬(¬((¬P¬Q)(PQ)))()¬(¬(¬P¬Q)¬(PQ)).(·)

题目2

image-20230322153228828

(1)

P(QR)¬(PQ)R(1 )(¬P¬Q)R.(·)

(2)

¬(PQ)R¬(¬(PR)¬(¬QR)).(1 )

(3)

PQ¬(¬(PQ))()(A)¬(¬P¬Q).(·)
¬P¬Q¬(¬(¬P)¬(¬Q))( A)(B)¬(PQ).()

从而,

PQ(¬P¬Q)(PQ)(1 )¬(PQ)¬(¬P¬Q).( AB)

题目3

image-20230322172059117

(1)

(¬PQ)(¬QP)¬(¬PQ)(¬QP)()¬(¬¬PQ)(¬QP)()¬(PQ)(¬QP)()(¬P¬Q)(¬QP)(·)((¬P¬Q)¬Q)P( )¬QP()(1)P¬Q,( )

即原公式的析取范式是 P¬Q. 同时它也是合取范式.

(2)

¬(¬PQ)QP¬QQ(·)PQ¬Q,( )

即原公式的合取范式是 PQ¬Q,同时它也是析取范式.

(3)

(P(QR))(PQR)¬(P(QR))(PQR)()(¬P¬(QR))PQR(· )(¬P(¬Q¬R))PQR(·)(¬P¬Q)(¬P¬R)PQR( )(¬P¬Q)(¬P¬R)P((P¬P)Q)((P¬P)R)()(¬P¬Q)(¬P¬R)P(PQ)(¬PQ)(PR)(¬PR)( )(¬P(¬QQ))(¬P(¬QQ))(P(PQ)(PR))(  )(¬PT)(¬PT)P()¬PP,( )

即原公式的析取范式是 (¬P¬Q)(¬P¬R)PQR¬PP

合取范式是 ¬PP.

HW3

题目1

image-20230329134534448

(1)

PQRPQ(PQ)R
00000
00100
01010
01111
10010
10111
11010
11111

主析取范式为

m3m5m7=(¬PQR)(P¬QR)(PQR),

主合取范式为

M0M1M2M4M6=(PQR)(PQ¬R)(P¬QR)(¬PQR)(¬P¬QR).

(2)

PQRPQRP(PQR)
00001
00111
01011
01111
10011
10111
11011
11111

主析取范式为

i=07mi=(¬P¬Q¬R)(¬P¬QR)(¬PQ¬R)(¬PQR)(P¬Q¬R)(P¬QR)(PQ¬R)(PQR),

主合取范式为 .

(3)

PQ¬PQ¬P¬(Q¬P)¬(Q¬P)¬P
001100
011100
100100
110010

主析取范式为 ,主合取范式为

i=03Mi=(PQ)(P¬Q)(¬PQ)(¬P¬Q).

题目2

image-20230329141250101

主析取范式为

m0m2m7=(¬P¬Q¬R)(¬PQ¬R)(PQR),

主合取范式为

M1M3M4M5M6=(PQ¬R)(P¬Q¬R)(¬PQR)(¬PQ¬R)(¬P¬QR).

题目3

image-20230329141746850

主合取范式为

M2M3M7=(¬PQ¬R)(¬PQR)(PQR),

主析取范式为

m0m1m4m5m6=(PQR)(PQ¬R)(¬PQR)(¬PQ¬R)(¬P¬QR).

HW4

题目1

image-20230417142455721

(1)

PQ(PQ)T()(PQ)(R¬R)()(PQR)(PQ¬R)()m6m7,
RTR()(Q¬Q)R()(QR)(¬QR)()T((QR)(¬QR))()(P¬P)((QR)(¬QR))()(P((QR)(¬QR)))(¬P((QR)(¬QR)))()(PQR)(P¬QR)(¬PQR)(¬P¬QR)()m1m3m5m7,
(PQ)Rm1m3m5m6m7( )(¬P¬QR)(¬PQR)(P¬QR)(PQ¬R)(PQR)M0M2M4(PQR)(P¬QR)(¬PQR).

(2)

(PQ)(QR)(¬PQ)(¬QR)()(¬P¬Q)(¬PR)(Q¬Q)(QR)()(¬P¬Q)(¬PR)F(QR)()(¬P¬Q)(¬PR)(QR)()(¬P¬QT)(¬PRT)(QRT)()((¬P¬Q)(R¬R))((¬PR)(Q¬Q))((QR)(P¬P))()(¬P¬QR)(¬P¬Q¬R)(¬PQR)(¬P¬QR)(PQR)(¬PQR)()m0m1m3m7( )(¬P¬Q¬R)(¬P¬QR)(¬PQR)(PQR)M2M4M5M6(P¬QR)(¬PQR)(¬PQ¬R)(¬P¬QR).

题目2

image-20230417150901216

(PQ)(PR)(¬PQ)(¬PR)()(¬P¬P)(¬PR)(¬PQ)(QR)()(¬P)(¬PR)(¬PQ)(QR)( )(¬P)(¬PQ)(QR)()(1)(¬P)(QR)()(¬P)(T(QR))()(¬P)((¬PP)(QR))()(¬P)(¬PQR)(PQR)()(¬P)(PQR)()(¬P(Q¬Q)(R¬R))(PQR)()(¬P¬Q¬R)(¬P¬QR)(¬PQ¬R)(¬PQR)(PQR)()(2)m0m1m2m3m7M4M5M6(¬PQR)(¬PQ¬R)(¬P¬QR).
P(QR)¬P(QR)()m0m1m2m3m7((1)(2))M4M5M6(¬PQR)(¬PQ¬R)(¬P¬QR).

题目3

image-20230417155250506

所求公式 GG1G2G3,其中 G1ACG2B¬CG3¬C(AB).

G1AC¬AC,()
G2B¬C¬B¬C,()
G3¬C(AB)¬(¬C)(AB)()ABC,()

从而

GG1G2G3(¬AC)(¬B¬C)(ABC)()((¬A¬B)(¬A¬C)(¬BC)(C¬C))(ABC)()((¬A¬B)(¬A¬C)(¬BC)F)(ABC)()((¬A¬B)(¬A¬C)(¬BC))(ABC)()(A¬A¬B)(A¬A¬C)(A¬BC)(¬AB¬B)(¬AB¬C)(B¬BC)(¬A¬BC)(¬AC¬C)(¬BCC)()(F¬B)(F¬C)(A¬BC)(¬AF)(¬AB¬C)(FC)(¬A¬BC)(¬AF)(¬BC)( )FF(A¬BC)F(¬AB¬C)F(¬A¬BC)F(¬BC)()(A¬B