Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
1. We define a logical connective as follows: P↓ Q is true when both P and Q are false, and it is false otherwise. (We read P Q as "P nor Q"). (a) Write a truth table for P Q and check that P Q is logically equivalent to ¬(PVQ). (b) Check that P↓ Q = Q ↓ P. That is, is commutative. (c) Show that (P ↓ Q) ↓ R and P↓ (QR) are logically inequivalent. That is, is not associative. (d) Show that the logical connectives, A, and V can each be expressed entirely in terms of ↓, without using any other logical connectives. Specifically, prove the following: i. ¬P = (PP). PAQ=(PP) ↓ (Q ↓ Q). iii. PVQ = (P↓ Q) ↓ (P ↓ Q). (e) Prove that the logical connective ⇒ can be expressed entirely in terms of ↓. That is, show that the sentence P⇒ Q is logically equivalent to a sentence involving ↓ and no other logical connectives.

1. We define a logical connective as follows: P↓ Q is true when both P and Q are false, and it is false otherwise. (We read P Q as "P nor Q"). (a) Write a truth table for P Q and check that P Q is logically equivalent to ¬(PVQ). (b) Check that P↓ Q = Q ↓ P. That is, is commutative. (c) Show that (P ↓ Q) ↓ R and P↓ (QR) are logically inequivalent. That is, is not associative. (d) Show that the logical connectives, A, and V can each be expressed entirely in terms of ↓, without using any other logical connectives. Specifically, prove the following: i. ¬P = (PP). PAQ=(PP) ↓ (Q ↓ Q). iii. PVQ = (P↓ Q) ↓ (P ↓ Q). (e) Prove that the logical connective ⇒ can be expressed entirely in terms of ↓. That is, show that the sentence P⇒ Q is logically equivalent to a sentence involving ↓ and no other logical connectives.

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question

Got a b and c done need help with d and e please show work 

**Step 1** **Disclaimer:** Since you have posted a question with multiple sub-parts, we will solve the first three sub-parts for you. To get the remaining sub-parts solved, please repost the complete question and mention the sub-parts to be solved. The logical symbol "∨" is used to denote "OR". The logical symbol "↓" is used to denote "NOT". Any two propositions are said to be logically equivalent if the truth value in each row of the truth table is the same for both propositions. **(a)** It is provided that P↓Q is true if both P, Q are false and false in all other scenarios. Use this data to make the truth table of P↓Q as follows. | P | Q | P↓Q | |---|---|-----| | T | T | F | | T | F | F | | F | T | F | | F | F | T | Make the truth table of ¬P∨Q as follows. | P | Q | P∨Q | ¬P∨Q | |---|---|-----|------| | T | T | T | F | | T | F | T | F | | F | T | T | T | | F | F | F | T | Comparing the last columns of both truth tables, it can be concluded that the expressions: P↓Q and ¬P∨Q are logically equivalent. **(b)** Make the truth table of Q↓P as follows. | P | Q | Q↓P | |---|---|-----| | T | T | F | | T | F | F | | F | T | F | | F | F | T | Comparing the last columns of both truth tables, it can be concluded that the expressions: P↓Q and Q↓P are logically equivalent. Hence, ↓ is commutative. **(c)** Make the truth table of P↓Q↓R and P↓(Q↓R) as follows. | P | Q | R | P↓Q | P↓Q↓R | Q↓R | P↓(Q↓R) | |---|---|---|-----|-------|-----|---------| | T | T | T | F | F | F | F
Transcribed Image Text:**Step 1** **Disclaimer:** Since you have posted a question with multiple sub-parts, we will solve the first three sub-parts for you. To get the remaining sub-parts solved, please repost the complete question and mention the sub-parts to be solved. The logical symbol "∨" is used to denote "OR". The logical symbol "↓" is used to denote "NOT". Any two propositions are said to be logically equivalent if the truth value in each row of the truth table is the same for both propositions. **(a)** It is provided that P↓Q is true if both P, Q are false and false in all other scenarios. Use this data to make the truth table of P↓Q as follows. | P | Q | P↓Q | |---|---|-----| | T | T | F | | T | F | F | | F | T | F | | F | F | T | Make the truth table of ¬P∨Q as follows. | P | Q | P∨Q | ¬P∨Q | |---|---|-----|------| | T | T | T | F | | T | F | T | F | | F | T | T | T | | F | F | F | T | Comparing the last columns of both truth tables, it can be concluded that the expressions: P↓Q and ¬P∨Q are logically equivalent. **(b)** Make the truth table of Q↓P as follows. | P | Q | Q↓P | |---|---|-----| | T | T | F | | T | F | F | | F | T | F | | F | F | T | Comparing the last columns of both truth tables, it can be concluded that the expressions: P↓Q and Q↓P are logically equivalent. Hence, ↓ is commutative. **(c)** Make the truth table of P↓Q↓R and P↓(Q↓R) as follows. | P | Q | R | P↓Q | P↓Q↓R | Q↓R | P↓(Q↓R) | |---|---|---|-----|-------|-----|---------| | T | T | T | F | F | F | F
1. We define a logical connective ↓ as follows: \( P \downarrow Q \) is true when both \( P \) and \( Q \) are false, and it is false otherwise. (We read \( P \downarrow Q \) as “P nor Q”). (a) Write a truth table for \( P \downarrow Q \) and check that \( P \downarrow Q \) is logically equivalent to \(\neg(P \lor Q)\). (b) Check that \( P \downarrow Q \equiv Q \downarrow P \). That is, ↓ is commutative. (c) Show that \( (P \downarrow Q) \downarrow R \) and \( P \downarrow (Q \downarrow R) \) are logically inequivalent. That is, ↓ is not associative. (d) Show that the logical connectives \(\neg\), \(\land\), and \(\lor\) can each be expressed entirely in terms of ↓, without using any other logical connectives. Specifically, prove the following: i. \(\neg P \equiv (P \downarrow P)\). ii. \(P \land Q \equiv (P \downarrow P) \downarrow (Q \downarrow Q)\). iii. \(P \lor Q \equiv (P \downarrow Q) \downarrow (P \downarrow Q)\). (e) Prove that the logical connective \(\Rightarrow\) can be expressed entirely in terms of ↓. That is, show that the sentence \( P \Rightarrow Q \) is logically equivalent to a sentence involving ↓ and no other logical connectives.
Transcribed Image Text:1. We define a logical connective ↓ as follows: \( P \downarrow Q \) is true when both \( P \) and \( Q \) are false, and it is false otherwise. (We read \( P \downarrow Q \) as “P nor Q”). (a) Write a truth table for \( P \downarrow Q \) and check that \( P \downarrow Q \) is logically equivalent to \(\neg(P \lor Q)\). (b) Check that \( P \downarrow Q \equiv Q \downarrow P \). That is, ↓ is commutative. (c) Show that \( (P \downarrow Q) \downarrow R \) and \( P \downarrow (Q \downarrow R) \) are logically inequivalent. That is, ↓ is not associative. (d) Show that the logical connectives \(\neg\), \(\land\), and \(\lor\) can each be expressed entirely in terms of ↓, without using any other logical connectives. Specifically, prove the following: i. \(\neg P \equiv (P \downarrow P)\). ii. \(P \land Q \equiv (P \downarrow P) \downarrow (Q \downarrow Q)\). iii. \(P \lor Q \equiv (P \downarrow Q) \downarrow (P \downarrow Q)\). (e) Prove that the logical connective \(\Rightarrow\) can be expressed entirely in terms of ↓. That is, show that the sentence \( P \Rightarrow Q \) is logically equivalent to a sentence involving ↓ and no other logical connectives.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Uncertainty Problems
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS