I Translate compound proposition p → q (implication) to p↓q question

AI Thread Summary
The discussion focuses on translating the logical implication p → q into a form using only the NOR operator (↓). The user successfully derives one equivalent expression but is confused about simplifying it to another form found in the solution manual. The manual's expression, F ↓ ((F ↓ q) ↓ q), raises questions about its logical equivalence to the user's derived expression, particularly regarding the absence of p and q in the final form. Clarification is provided that p ↓ p represents the negation of p, and additional resources are suggested for understanding NOR logic. The conversation emphasizes the nuances of logical equivalence in discrete mathematics.
VinnyW
Messages
4
Reaction score
0
TL;DR Summary
How to simplify ((p ↓ p) ↓ q) ↓ (p ↓ p) ↓ q) ) to F ↓ (( F ↓ q ) ↓ q ), whereas p and q are atomic propositions and F, probably, is contradiction.
I hope someone can help me or point me in the right direction.

I am reading Discrete Mathematics with its Applications by Rosen. I am trying to self learn discrete math. I am actually able to do most questions but I have a question about a solution (not the question itself.)

The question is (Section 1.3 Foundations: Logic and Proofs. Question 51)

Question: Find a compound proposition logically equivalent to p → q using only the logical operator ↓

My answer
:

I know

p → q ≡ ¬ p ∨ q

and

p ↓ p ≡ ¬ p

By combining them, I got the answer:

((p ↓ p) ↓ q) ↓ (p ↓ p) ↓ q) )

which is the same answer as the one in the solution manual; however, the manual also lists:

F ↓ (( F ↓ q ) ↓ q )

I know F is contradiction.

How can I simplify

((p ↓ p) ↓ q) ↓ (p ↓ p) ↓ q) )

to

F ↓ (( F ↓ q ) ↓ q )
 
Physics news on Phys.org
I'm confused, the last expression has no dependency on p at all? That can't possibly be the same thing logically.
 
VinnyW said:
Summary:: How to simplify ((p ↓ p) ↓ q) ↓ (p ↓ p) ↓ q) ) to F ↓ (( F ↓ q ) ↓ q ), whereas p and q are atomic propositions and F, probably, is contradiction.

p ↓ p ≡ ¬ p
What does the notation p ↓ p mean, particularly the down arrow? I've never seen that notation before.
 
It means nor
 
The following page should be useful in that case:
https://en.wikipedia.org/wiki/NOR_logic

In "boolean algebra" notation we get the following as equivalent (following the above page):
##p \rightarrow q##
##p'+q##
##(p \,\, \mathrm{nor} \,\, p)+q##

Now one can expand the last expression using the "OR gate" equivalence.
 
Back
Top