MHB What is the Implication of a Formula in Propositional Calculus?

[solakis1]

Given : $$p\wedge\neg (q\vee r)$$ then prove whether this formula implies:!) $$(p\wedge\neg q)\vee (p\wedge\neg r)$$

OR

2) $$(p\wedge\neg q)\wedge (p\wedge\neg r)$$

 

[Monoxdifly]

Spoiler

$$p\wedge\neg (q\vee r)$$
=$$p\wedge(\neg q\wedge\neg r)$$
=$$(p\wedge\neg q)\wedge (p\wedge\neg r)$$

So, it implies 2)

 

[solakis1]

Spoiler

$$p\wedge\neg (q\vee r)$$
=$$p\wedge(\neg q\wedge\neg r)$$
=$$(p\wedge\neg q)\wedge (p\wedge\neg r)$$

So, it implies 2)

Spoiler

Sorry,but i am trying to find out how you got $$(p\wedge\neg q)\wedge (p\wedge\neg r)$$ from

$$p\wedge(\neg q\wedge\neg r)$$

 

[Olinguito]

Spoiler

Sorry,but i am trying to find out how you got $$(p\wedge\neg q)\wedge (p\wedge\neg r)$$ from

$$p\wedge(\neg q\wedge\neg r)$$

Spoiler

And ($\wedge$) is distributive over itself since it is associative, commutative and idempotent: https://proofwiki.org/wiki/Associative_Commutative_Idempotent_Operation_is_Distributive_over_Itself.

 

[solakis1]

Spoiler

And ($\wedge$) is distributive over itself since it is associative, commutative and idempotent: https://proofwiki.org/wiki/Associative_Commutative_Idempotent_Operation_is_Distributive_over_Itself.

Spoiler

If the system is associative ,then

(A*B)*C =A*(B*C)...(1) ,Note i use * instead the circle,where A,B,C are elements of the structure

And if we put :

A=a
B=b
C=(a*c), then by using (1) we have

(a*b)*(a*c)= a*[b*(a*c)]

Now where wiki gets : (a*b)*(a*c)=a*(b*a)*c ??

 

[Olinguito]

Spoiler

(a*b)*(a*c)= a*[b*(a*c)]

Now where wiki gets : (a*b)*(a*c)=a*(b*a)*c ??

Aren’t the expressions in red equal?

 

[solakis1]

Spoiler

Aren’t the expressions in red equal?

Spoiler

By using associativity you can get them equal.

But i am asking ,how wiki gets, a*(b*a)*c from (a*b)*(a*c) by ‹using associativity

Parenthesis are very important in this kind of proof otherwise a lot of wrong proofs can be given

Look at the following proof:

(a*b)*(a*c)= (a*a)*b*c=............By commutativity

=a*b*c.................By indepondency

 

[I like Serena]

Spoiler

By using associativity you can get them equal.

But i am asking ,how wiki gets, a*(b*a)*c from (a*b)*(a*c) by ‹using associativity

Parenthesis are very important in this kind of proof otherwise a lot of wrong proofs can be given

Look at the following proof:

(a*b)*(a*c)= (a*a)*b*c=............By commutativity

=a*b*c.................By indepondency

Spoiler

If we do not have associativity, parentheses are indeed very important.
If we do have associativity, parentheses are redundant, and often left out.
In this case we have associativity, don't we?

 

[solakis1]

Spoiler

If we do not have associativity, parentheses are indeed very important.
If we do have associativity, parentheses are redundant, and often left out.
In this case we have associativity, don't we?

Spoiler

Can you give an example of a system with a binary opperation where by using associativity you can prove that parenthesis are redundant

 

[Olinguito]

Spoiler

Can you give an example of a system with a binary opperation where by using associativity you can prove that parenthesis are redundant

Spoiler

Use induction with a general expression like $a_1\circ a_2\circ\cdots\circ a_n$.

Obviously parentheses are redundant when $n=1$ or $n=2$. By the definition of associativity, they are redundant for $n=3$.

Suppose they are redundant for some $n$ and all $r$ with $3\leqslant r\leqslant n$. Consider the expression $a_1\circ\cdots\circ a_n\circ a_{n+1}$. You can have either
$$\left(a_1\circ\cdots\circ a_n\right)\circ a_{n+1}$$
or
$$\left(a_1\circ\cdots\circ a_i\right)\circ\left(a_{i+1}\circ\cdots\circ a_n\circ a_{n+1}\right)$$
(where $1\leqslant i\leqslant n-1$). In either case, the inductive hypothesis applies to all the expressions within parentheses; hence, by induction, parentheses are redundant.

So when you have an associative operation, it doesn’t matter how long the string is: you get the same answer no matter how you bracket it up.

 

[solakis1]

Spoiler

$$p\wedge\neg (q\vee r)$$
=$$p\wedge(\neg q\wedge\neg r)$$
=$$(p\wedge\neg q)\wedge (p\wedge\neg r)$$

So, it implies 2)

Spoiler

The following truth table indicates that it implies both (1) and (2)[TABLE="class: truth"]
[TR]
[TH="align: center"]p[/TH]
[TH="align: center"]q[/TH]
[TH="align: center"]r[/TH]
[TH="class: dv, align: center"][/TH]
[TH="align: center"][/TH]
[TH="align: center"][/TH]
[TH="align: center"]([/TH]
[TH="align: center"]p[/TH]
[TH="align: center"]&[/TH]
[TH="align: center"]~[/TH]
[TH="align: center"]([/TH]
[TH="align: center"]q[/TH]
[TH="align: center"]∨[/TH]
[TH="align: center"]r[/TH]
[TH="align: center"])[/TH]
[TH="align: center"])[/TH]
[TH="align: center"]→[/TH]
[TH="align: center"]([/TH]
[TH="align: center"]([/TH]
[TH="align: center"]p[/TH]
[TH="align: center"]&[/TH]
[TH="align: center"]~[/TH]
[TH="align: center"]q[/TH]
[TH="align: center"])[/TH]
[TH="align: center"]∨[/TH]
[TH="align: center"]([/TH]
[TH="align: center"]p[/TH]
[TH="align: center"]&[/TH]
[TH="align: center"]~[/TH]
[TH="align: center"]r[/TH]
[TH="align: center"])[/TH]
[TH="align: center"])[/TH]
[TH="align: center"][/TH]
[/TR]
[TR]
[TD]T[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD="class: dv"][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD][/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD][/TD]
[TD][/TD]
[TD="class: mc"]T[/TD]
[TD][/TD]
[TD][/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD][/TD]
[TD]F[/TD]
[TD][/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]T[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD="class: dv"][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD][/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD][/TD]
[TD][/TD]
[TD="class: mc"]T[/TD]
[TD][/TD]
[TD][/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD][/TD]
[TD]T[/TD]
[TD][/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]T[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD="class: dv"][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD][/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD][/TD]
[TD][/TD]
[TD="class: mc"]T[/TD]
[TD][/TD]
[TD][/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD][/TD]
[TD]T[/TD]
[TD][/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]T[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD="class: dv"][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD][/TD]
[TD][/TD]
[TD="class: mc"]T[/TD]
[TD][/TD]
[TD][/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD][/TD]
[TD]T[/TD]
[TD][/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]F[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD="class: dv"][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD][/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD][/TD]
[TD][/TD]
[TD="class: mc"]T[/TD]
[TD][/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD][/TD]
[TD]F[/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]F[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD="class: dv"][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD][/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD][/TD]
[TD][/TD]
[TD="class: mc"]T[/TD]
[TD][/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD][/TD]
[TD]F[/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD="class: dv"][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD][/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD]T[/TD]
[TD][/TD]
[TD][/TD]
[TD="class: mc"]T[/TD]
[TD][/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD]F[/TD]
[TD][/TD]
[TD]F[/TD]
[TD][/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]F[/TD]
[TD]T[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]