Yioop - PHP Search Engine

Oct 18 In-Class Exercise.

Post your solutions to the Oct. 20 In-Class Exercise to this thread.

Best,

Chris

Post your solutions to the Oct. 20 In-Class Exercise to this thread. Best, Chris

-- Oct 18 In-Class Exercise

PHP23-> {{P11,P12},{P21,P22},{P31,P32},{~P11,~P21},{~P11,~P31},{~P21,~P31},{~P12,~P22},{~P12,~P32},{~P22,~P32}

If P11 is True
```
 -------------------
```
R01: P11
R02: {~P11,~P21}
R03: ~P21
R04: {P21,P22}
R05: P22
R06: {~P11,~P31}
R07: ~P31
R08: {P31,P32}
R09: P32
R10: {~P22,~P32}
R11: {}
```
 
```
If P11 is False
```
 ------------------
```
R01: ~P11
R02: {P11,P12}
R03: P12
R04: {~P12,~P22}
R05: ~P22
R06: {P21,P22}
R07: P21
R08: {~P12,~P32}
R09: ~P32
R10: {P31,P32}
R11: P31
R12: {~P21,~P31}
R13: {}

Combination
```
 ------------------
```
R01: {P1,~P1}
```
 .
 .
 .
```
R02: {}

PHP23-> {{P11,P12},{P21,P22},{P31,P32},{~P11,~P21},{~P11,~P31},{~P21,~P31},{~P12,~P22},{~P12,~P32},{~P22,~P32} *If P11 is True ------------------- *R01: P11 *R02: {~P11,~P21} *R03: ~P21 *R04: {P21,P22} *R05: P22 *R06: {~P11,~P31} *R07: ~P31 *R08: {P31,P32} *R09: P32 *R10: {~P22,~P32} *R11: {} *If P11 is False ------------------ *R01: ~P11 *R02: {P11,P12} *R03: P12 *R04: {~P12,~P22} *R05: ~P22 *R06: {P21,P22} *R07: P21 *R08: {~P12,~P32} *R09: ~P32 *R10: {P31,P32} *R11: P31 *R12: {~P21,~P31} *R13: {} *Combination ------------------ *R01: {P1,~P1} . . . *R02: {}

-- Oct 18 In-Class Exercise

1) Write down the clauses for ¬PHP32
Clauses:

	{

	{p11, p12}, {p21, p22}, {p31, p32}, 

	{~p11, ~p21}, {~p11, ~p31}, {~p21, ~p31},
 
	{~p12, ~p22}, {~p12, ~p32}, {~p22, ~p32}

	}

2) What would be the set of clauses if p11 was True? Give a refutation for these clauses.
Clauses:

	{

	{p21, p22}, {p31, p32}, 

	{~p21}, {~p31}, {~p21, ~p31},
 
	{~p12, ~p22}, {~p12, ~p32}, {~p22, ~p32}

	}<br

Refutation:
R1: {p21, p22}
R2: {~p21}
R3: {p22} resolved from R1 and R2
R4: {~p31}
R5: {p31, p32}
R6: {p32} resolved from R4 and R5
R7: {~p22, ~p32}
R8: {~p32} resolved from R3 and R7
R9: {} resolved from R6 and R8

3) What would be the set of clauses if p11 was False? Give a refutation for these clauses.
Clauses:

	{

	{p12}, {p21, p22}, {p31, p32}, 

	{~p21, ~p31},
 
	{~p12, ~p22}, {~p12, ~p32}, {~p22, ~p32}

	}

Refutation:
R01: {~p12, ~p22}
R02: {p12}
R03: {~p22} resolved from R01 and R02
R04: {~p12, ~p32}
R05: {~p32} resolved from R02 and R04
R06: {p21, p22}
R07: {p21} resolved from R03 and R06
R08: {p31, p32}
R09: {p31} resolved from R05 and R08
R10: {~p21, ~p31}
R11: {~p21} resolved from R09 and R10
R12: {} resolved from R07 and R11

4) Figure out how to combine and modify these two proofs to give a refutation of ¬PHP32.
Clauses:

	{

	{p11, p12}, {p21, p22}, {p31, p32}, 

	{~p11, ~p21}, {~p11, ~p31}, {~p21, ~p31}, 

	{~p12, ~p22}, {~p12, ~p32}, {~p22, ~p32}

	}

Refutation:
Part 1: R1: {p21, p22}
R2: {~p11, ~p21}
R3: {~p11, p22} resolved from R1 and R2
R4: {~p11, ~p31}
R5: {p31, p32}
R6: {~p11, p32} resolved from R4 and R5
R7: {~p22, ~p32}
R8: {~p11, ~p32} resolved from R3 and R7
R9: {~p11} resolved from R6 and R8

Part 2:
R10: {~p12, ~p22}
R11: {p11, p12}
R12: {p11, ~p22} resolved from R10 and R11
R13: {~p12, ~p32}
R14: {p11, ~p32} resolved from R11 and R13
R15: {p21, p22}
R16: {p11, p21} resolved from R12 and R15
R17: {p31, p32}
R18: {p11, p31} resolved from R14 and R17
R19: {~p21, ~p31}
R20: {p11, ~p21} resolved from R18 and R19
R21: {p11} resolved from R16 and R20

Part 3:
R22: {} resolved from R9 and R21

(Edited: 2017-10-23)

1) Write down the clauses for ¬PHP32 Clauses: { {p11, p12}, {p21, p22}, {p31, p32}, {~p11, ~p21}, {~p11, ~p31}, {~p21, ~p31}, {~p12, ~p22}, {~p12, ~p32}, {~p22, ~p32} } 2) What would be the set of clauses if p11 was True? Give a refutation for these clauses. Clauses: { {p21, p22}, {p31, p32}, {~p21}, {~p31}, {~p21, ~p31}, {~p12, ~p22}, {~p12, ~p32}, {~p22, ~p32} } R1: {p21, p22} R2: {~p21} R3: {p22} resolved from R1 and R2 R4: {~p31} R5: {p31, p32} R6: {p32} resolved from R4 and R5 R7: {~p22, ~p32} R8: {~p32} resolved from R3 and R7 R9: {} resolved from R6 and R8 3) What would be the set of clauses if p11 was False? Give a refutation for these clauses. Clauses: { {p12}, {p21, p22}, {p31, p32}, {~p21, ~p31}, {~p12, ~p22}, {~p12, ~p32}, {~p22, ~p32} } Refutation: R01: {~p12, ~p22} R02: {p12} R03: {~p22} resolved from R01 and R02 R04: {~p12, ~p32} R05: {~p32} resolved from R02 and R04 R06: {p21, p22} R07: {p21} resolved from R03 and R06 R08: {p31, p32} R09: {p31} resolved from R05 and R08 R10: {~p21, ~p31} R11: {~p21} resolved from R09 and R10 R12: {} resolved from R07 and R11 4) Figure out how to combine and modify these two proofs to give a refutation of ¬PHP32. Clauses: { {p11, p12}, {p21, p22}, {p31, p32}, {~p11, ~p21}, {~p11, ~p31}, {~p21, ~p31}, {~p12, ~p22}, {~p12, ~p32}, {~p22, ~p32} } Refutation: Part 1: R1: {p21, p22} R2: {~p11, ~p21} R3: {~p11, p22} resolved from R1 and R2 R4: {~p11, ~p31} R5: {p31, p32} R6: {~p11, p32} resolved from R4 and R5 R7: {~p22, ~p32} R8: {~p11, ~p32} resolved from R3 and R7 R9: {~p11} resolved from R6 and R8 Part 2: R10: {~p12, ~p22} R11: {p11, p12} R12: {p11, ~p22} resolved from R10 and R11 R13: {~p12, ~p32} R14: {p11, ~p32} resolved from R11 and R13 R15: {p21, p22} R16: {p11, p21} resolved from R12 and R15 R17: {p31, p32} R18: {p11, p31} resolved from R14 and R17 R19: {~p21, ~p31} R20: {p11, ~p21} resolved from R18 and R19 R21: {p11} resolved from R16 and R20 Part 3: R22: {} resolved from R9 and R21

-- Oct 18 In-Class Exercise

{P11,P12} {P21,P22} {P31,P32} {~P11,~P21} {~P11,~P31} {~P21,~P31} {~P12,~P22} {~P12,~P32} {~P22,~P32}

——> when P11 is True

R01: P11 R02: {~P11,~P21} R03: ~P21 R04: {P21,P22} R05: P22 R06: {~P11,~P31} R07: ~P31 R08: {P31,P32} R09: P32 R10: {~P22,~P32}

——> when P11 is False

R01: ~P11 R02: {P11,P12} R03: P12 R04: {~P12,~P22} R05: ~P22 R06: {P21,P22} R07: P21 R08: {~P12,~P32} R09: ~P32 R10: {P31,P32} R11: P31 R12: {~P21,~P31}

{P11,P12} {P21,P22} {P31,P32} {~P11,~P21} {~P11,~P31} {~P21,~P31} {~P12,~P22} {~P12,~P32} {~P22,~P32} ——> when P11 is True R01: P11 R02: {~P11,~P21} R03: ~P21 R04: {P21,P22} R05: P22 R06: {~P11,~P31} R07: ~P31 R08: {P31,P32} R09: P32 R10: {~P22,~P32} ——> when P11 is False R01: ~P11 R02: {P11,P12} R03: P12 R04: {~P12,~P22} R05: ~P22 R06: {P21,P22} R07: P21 R08: {~P12,~P32} R09: ~P32 R10: {P31,P32} R11: P31 R12: {~P21,~P31}

-- Oct 18 In-Class Exercise

((resource:8FFF3C55-7234-4487-AA6D-AD22C82F4172.jpeg|Resource Description for 8FFF3C55-7234-4487-AA6D-AD22C82F4172.jpeg))

-- Oct 18 In-Class Exercise

PHP23: [(P11, P12); (P21,P22); (P31,P32);(~P11,~P21);(~P11,~P31);(~P21,~P31)

	(~P12, ~P22);(~P12,~P32); (~P22,~P32)]

if P11 is True: R01 = P11; R02 = (~P11,~P21); RO3 = ~P21; R04 = (P21,P22); R05 = P22; R06 = (~P11,~P31); R07 = ~P31; R08 = (~P31,~P32); R09 = P32; R10 = (~P22,~P32); R11 = ()

if P11 is False: R01 = ~P11; R02 = (P11,P21); RO3 = P21; R04 = (~P21,~P22); R05 = ~P22; R06 = (P21,P22); R07 = P21; R08 = (~P12,~P32); R09 = ~P32; R10 = (P31,P32); R11 = P31; R12 = (~P21,~P31); P13 = ()

Combination: R01 = (P1,~P1)...R02 = ()

PHP23: [(P11, P12); (P21,P22); (P31,P32);(~P11,~P21);(~P11,~P31);(~P21,~P31) (~P12, ~P22);(~P12,~P32); (~P22,~P32)] if P11 is True: R01 = P11; R02 = (~P11,~P21); RO3 = ~P21; R04 = (P21,P22); R05 = P22; R06 = (~P11,~P31); R07 = ~P31; R08 = (~P31,~P32); R09 = P32; R10 = (~P22,~P32); R11 = () if P11 is False: R01 = ~P11; R02 = (P11,P21); RO3 = P21; R04 = (~P21,~P22); R05 = ~P22; R06 = (P21,P22); R07 = P21; R08 = (~P12,~P32); R09 = ~P32; R10 = (P31,P32); R11 = P31; R12 = (~P21,~P31); P13 = () Combination: R01 = (P1,~P1)...R02 = ()

-- Oct 18 In-Class Exercise

  PHP32

  {p11, p12},{p21, p22},{p31, p32},

  {~p11, ~p21},{~p11, ~p31},{~p21, ~p31},
 
  {~p12, ~p22}, {~p12, ~p32},{~p22, ~p32}

  If  p11  is true

  R1 = {P11}
  R2 = {~P11, ~P21}
  R3 ={ P21}
  R4= {P21. P22}
  R5 ={ P22}
  R6 ={ ~P11, ~P31}
  R7 ={ ~P31}
  R8 = {P31, P32}
  R9 = {P32}
  R10 = {~P22, ~P32}

  If P11 is false

  R1 = {~P11}
  R2 = {P11, P21}
  R3 ={ P21}
  R4= {~P21. ~P22}
  R5 ={ ~P22}
  R6 ={ P11, P31}
  R7 ={ P31}
  R8 = {~P31, ~P32}
  R9 = {~P32}
  R10 = {P22, P32}
  R11:{P31}
  R12:{~P21, ~P31}

(Edited: 2017-10-18)

PHP32 {p11, p12},{p21, p22},{p31, p32}, {~p11, ~p21},{~p11, ~p31},{~p21, ~p31}, {~p12, ~p22}, {~p12, ~p32},{~p22, ~p32} If p11 is true R1 = {P11} R2 = {~P11, ~P21} R3 ={ P21} R4= {P21. P22} R5 ={ P22} R6 ={ ~P11, ~P31} R7 ={ ~P31} R8 = {P31, P32} R9 = {P32} R10 = {~P22, ~P32} If P11 is false R1 = {~P11} R2 = {P11, P21} R3 ={ P21} R4= {~P21. ~P22} R5 ={ ~P22} R6 ={ P11, P31} R7 ={ P31} R8 = {~P31, ~P32} R9 = {~P32} R10 = {P22, P32} R11:{P31} R12:{~P21, ~P31}

-- Oct 18 In-Class Exercise

 All Clauses:

{p11, p12},{p21, p22},{p31, p32},

 {~p11, ~p21},{~p11, ~p31},{~p21, ~p31},
 {~p12, ~p22}, {~p12, ~p32},{~p22, ~p32}

 if p11 is true
 The refutation:
 R1: {p21, p22}
 R2: {~p21}
 R3: {p22}        from R1 and R2
 R4: {~p31}
 R5: {p31, p32}
 R6: {p32}        from R4 and R5
 R7: {~p22, ~p32}
 R8: {~p32}         from R3 and R7
 R9: {}       from R6 and R8

 if p11 is false
 the refutation:

 R1: {~p22}
 R2: {p21, p22}
 R3: {p21}      from R1 and R2
 R4: {~p32}
 R5: {p31, p32}
 R6: {p31}       from R4 and R5
 R7: {~p21, ~p31}
 R8: {~p31}       from R3 and R7
 R9: {}       from R6 and R8

(Edited: 2017-10-18)

All Clauses: {p11, p12},{p21, p22},{p31, p32}, {~p11, ~p21},{~p11, ~p31},{~p21, ~p31}, {~p12, ~p22}, {~p12, ~p32},{~p22, ~p32} if p11 is true The refutation: R1: {p21, p22} R2: {~p21} R3: {p22} from R1 and R2 R4: {~p31} R5: {p31, p32} R6: {p32} from R4 and R5 R7: {~p22, ~p32} R8: {~p32} from R3 and R7 R9: {} from R6 and R8 if p11 is false the refutation: R1: {~p22} R2: {p21, p22} R3: {p21} from R1 and R2 R4: {~p32} R5: {p31, p32} R6: {p31} from R4 and R5 R7: {~p21, ~p31} R8: {~p31} from R3 and R7 R9: {} from R6 and R8

-- Oct 18 In-Class Exercise

Clauses:

  {p11, p12},{p21, p22},{p31, p32},

  {~p11, ~p21},{~p11, ~p31},{~p21, ~p31},

  {~p12, ~p22}, {~p12, ~p32},{~p22, ~p32}

 p11  =  true

  R1 = {P11}

  R2 = {~P11, ~P21}

  R3 ={ P21}

  R4= {P21. P22}

  R5 ={ P22}

  R6 ={ ~P11, ~P31}

  R7 ={ ~P31}

  R8 = {P31, P32}

  R9 = {P32}

  R10 = {~P22, ~P32}

p11 = false

  R1 = {~P11}

  R2 = {P11, P21}

  R3 ={ P21}

  R4= {~P21. ~P22}

  R5 ={ ~P22}

  R6 ={ P11, P31}

  R7 ={ P31}

  R8 = {~P31, ~P32}

  R9 = {~P32}

  R10 = {P22, P32}

  R11:{P31}

  R12:{~P21, ~P31}

Archana Yadawa

(Edited: 2017-10-18)

Clauses: {p11, p12},{p21, p22},{p31, p32}, {~p11, ~p21},{~p11, ~p31},{~p21, ~p31}, {~p12, ~p22}, {~p12, ~p32},{~p22, ~p32} p11 = true R1 = {P11} R2 = {~P11, ~P21} R3 ={ P21} R4= {P21. P22} R5 ={ P22} R6 ={ ~P11, ~P31} R7 ={ ~P31} R8 = {P31, P32} R9 = {P32} R10 = {~P22, ~P32} p11 = false R1 = {~P11} R2 = {P11, P21} R3 ={ P21} R4= {~P21. ~P22} R5 ={ ~P22} R6 ={ P11, P31} R7 ={ P31} R8 = {~P31, ~P32} R9 = {~P32} R10 = {P22, P32} R11:{P31} R12:{~P21, ~P31} Archana Yadawa

-- Oct 18 In-Class Exercise

clauses: {

		{p11, p12}, {p21, p22}, {p31, p32},

		{~p11, ~p21}, {~p11, ~p31}, {~p12, ~p22}

                 {~p12, ~p32}, {~p21, ~p31}, {~p22, ~p32}

}

clauses when p11 is true: {

		{p21, p22}, {p31, p32},

		{~p21}, {~p31}, {~p12, ~p22}

                 {~p12, ~p32}, {~p21, ~p31}, {~p22, ~p32}

}

Resolution refutation:

R1: {p21, p22}

R2: {p31, p32}

R3: {~p21}

R4: {~p31}

R5: {~p22, ~p32}

R6: {P22} resolved from R1 and R3

R7: {P32} resolved from R2 and R4

R8: {~P32} resolved from R6 and R5

R9: {} resolved from R7 and R8

clauses when p11 is false: {

		{p12}, {p21, p22}, {p31, p32},

		{~p11, ~p21}, {~p11, ~p31}, {~p22}

                 {~p32}, {~p21, ~p31}, {~p22, ~p32}

}

resolution refutation:

R1: {p21, p22}

R2: {p31, p32}

R3: {~p22}

R4: {~p32}

R5: {~p21, ~p31}

R6: {p21} resolved from R1 and R3

R7: {p31} resolved from R2 and R4

R8: {~p31} resolved from R5 and R7

R9: {} resolved from R7 and R8

combination resolution:

R1: {p21, p22}

R2: {p31, p32}

R3: {~p11, ~p21}

R4: {~p11, ~p31}

R5: {~p22, ~p32}

R6: {~p11, p22} resolved from R1 and R3

R7: {~p11, P32} resolved from R2 and R4

R8: {~p11, ~P32} resolved from R6 and R5

R9: {~p11} resolved from R7 and R8

———————

R10: {~p12, ~p22}

R11: {~p12, ~p32}

R12: {~p21, ~p31}

R13: {~p12, p21} resolved from R1 and R10

R14: {~p12, p31} resolved from R2 and R11

R15: {~p12, ~p21} resolved from R12 and R14

R16: {~p12} resolved from R13 and R15

————

R17: {p11, p12}

R18: {p12} R9 and R17

R19: {} R16 and R18

(Edited: 2017-10-23)

clauses: { {p11, p12}, {p21, p22}, {p31, p32}, {~p11, ~p21}, {~p11, ~p31}, {~p12, ~p22} {~p12, ~p32}, {~p21, ~p31}, {~p22, ~p32} } clauses when p11 is true: { {p21, p22}, {p31, p32}, {~p21}, {~p31}, {~p12, ~p22} {~p12, ~p32}, {~p21, ~p31}, {~p22, ~p32} } Resolution refutation: R1: {p21, p22} R2: {p31, p32} R3: {~p21} R4: {~p31} R5: {~p22, ~p32} R6: {P22} resolved from R1 and R3 R7: {P32} resolved from R2 and R4 R8: {~P32} resolved from R6 and R5 R9: {} resolved from R7 and R8 clauses when p11 is false: { {p12}, {p21, p22}, {p31, p32}, {~p11, ~p21}, {~p11, ~p31}, {~p22} {~p32}, {~p21, ~p31}, {~p22, ~p32} } resolution refutation: R1: {p21, p22} R2: {p31, p32} R3: {~p22} R4: {~p32} R5: {~p21, ~p31} R6: {p21} resolved from R1 and R3 R7: {p31} resolved from R2 and R4 R8: {~p31} resolved from R5 and R7 R9: {} resolved from R7 and R8 combination resolution: R1: {p21, p22} R2: {p31, p32} R3: {~p11, ~p21} R4: {~p11, ~p31} R5: {~p22, ~p32} R6: {~p11, p22} resolved from R1 and R3 R7: {~p11, P32} resolved from R2 and R4 R8: {~p11, ~P32} resolved from R6 and R5 R9: {~p11} resolved from R7 and R8 ——————— R10: {~p12, ~p22} R11: {~p12, ~p32} R12: {~p21, ~p31} R13: {~p12, p21} resolved from R1 and R10 R14: {~p12, p31} resolved from R2 and R11 R15: {~p12, ~p21} resolved from R12 and R14 R16: {~p12} resolved from R13 and R15 ———— R17: {p11, p12} R18: {p12} R9 and R17 R19: {} R16 and R18