[Math] Creating a proposition from a truth table using only ~ ⋀ and v

logicpropositional-calculus

I have to find a simple expression for the third column in the truth table using only the logical connectives I've mention above. There are two questions that are involved here.

Problem 1:

Truth table relating to the first problem:

enter image description here

Part 1

All expressions in which p and q return true.

Row 1:  p ⋀ q
Row 3: ~p ⋀ q
Row 4: ~p ⋀ ~q

Thus the expression that satisfy each outcome is: (p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q)

Simplified Expression: 
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ (p ⋀ q) ⋁ (~p ⋀ q) ⋁ ~(p ⋁ q)
 DeMorgan’s Law 
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ (p ⋀ q) ⋁ (~p ⋀ q) ⋁ ~(q ⋁ p)
 Commutative Law
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ ((p ⋀ q) ⋁ ~p) ⋀ ((q ⋁ ~q) ⋁ p)
 Associative Law
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ ((p ⋀ q) ⋁ ~p) ⋀ (True ⋁ p)
 Definition of ⋁
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ ((p ⋀ q) ⋁ ~p) ⋀ True
 Definition of ⋁
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ ((~p ⋁ p) ⋀ (~p ⋁ q))  ⋀ True
 Distributive Law
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ (True ⋀ (~p ⋁ q))  ⋀ True
 P ⋀ True ≡ P
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ (~p ⋁ q)  ⋀ True
 P ⋀ True ≡ P
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ (~p ⋁ q)

Note: I already knew that the answer was (~p v q) but I had to show how I got there.

Problem 2:

Here is the truth table relating to problem number 2:

enter image description here

Part 2 

Row 2:  p ⋀ ~q
Row 3: ~p ⋀ q

Thus the expression that satisfy each outcome is: (p ⋀ ~q) ⋁ (~p ⋀ q)

Simplified Expression:
(p ⋀ ~q) ⋁ (~p ⋀ q)  ≡ (~p ⋁ ~q) ⋀ (p ⋁ q) 
Rewrite the expression in a conjunction format.
(p ⋀ ~q) ⋁ (~p ⋀ q)  ≡ ~(p ⋀ q) ⋀ (p ⋁ q) 
DeMorgan’s Law
(p ⋀ ~q) ⋁ (~p ⋀ q)  ≡ ~(p ⋀ q) ⋀ (p ⋁ q)

Note: I'm not sure if it's possible to simply further

All I'm asking is for someone to check if the steps that I took are right.

Edit: New proof for number 1 please verify!

(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ (p ⋀ q) ⋁ ~p ⋀ (~q ⋁ q) Distributive Law
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ (p ⋀ q) ⋁ ~p ⋀ T Definition of v 
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ (p ⋀ q) ⋁ ~p Definition of and
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ ~p  ⋁ (p ⋀ q) commutative Law 
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ (~p ⋁ p) ⋀ (~p ⋁ q) Distributive Law
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ True ⋀ (~p ⋁ q) definition of v 
(p ⋀ q) ⋁ (~p ⋀ q) ⋁ (~p ⋀ ~q) ≡ ~p ⋁ q definition of and

Best Answer

A way to check that such steps are correct can get understood by writing out the specific use of the logical laws you've used, and then highlighting in some way via underlining or circling where you made the replacement. I'll provide an example.

I use Polish notation. So, your first problem starts with

A A Kpq KNpq K NpNq.

You use the De Morgan's law which says that

K NxNy = NA x y in your first step.

Thus, we'll highlight the relevant part of the relevant formula.

A A Kpq KNpq K NpNq.

And substituting in De Morgan's law we have

K NpNq = NA p q.

Now making the replacement we see that

A A Kpq KNpq NA p q is correct.

In your problem you say that

"(p ⋀ q) ⋁ (~p ⋀ q) ⋁ ~(q ⋁ p)"

leads to

"((p ⋀ q) ⋁ ~p) ⋀ ((q ⋁ ~q) ⋁ p)"

via the associative law (for ⋁?).

I don't follow. Which part did you replace? To me it looks like the first part you replaced was the parentheses with a blank. You replaced

"(~p ⋀ q) ⋁ ~(q ⋁ p)" with "~p) ⋀ ((q ⋁ ~q) ⋁ p)". I'm very sure that no law allows you to do that.

You went from

" ((p ⋀ q) ⋁ ~p) ⋀ True"

to

"((~p ⋁ p) ⋀ (~p ⋁ q)) ⋀ True"

You can do that, but I encourage you to look at the relevant distributive law more closely. I suspect you'll find it doesn't allow you to do exactly what you did here... you need another law invoked also.

Related Question