Skip to main content

Proving a Proposition is a Tautology in Discrete Math: Example

Proofs aren't always easy to write out but I'll attempt a lengthier proof that I've recently seen. The assertion is that the proposition [p → (q → r)] → [(p → q) → (p → r)] is a tautology. We can approach this in a couple of different ways. One way would be to create a truth table, which I'll demonstrate below and the other will be to do it with inference laws. I'm not going to list out all of the inference laws, but will instead just work out the example.

The truth table should display True for all of the different combinations and as can be seen below it does.
p
q
r
q → r
p → (q → r)
p → q
p → r
(p → q) → (p → r)
[p → (q → r)] →
[(p → q) → (p → r)]
T
T
T
T
T
T
T
T
T
T
T
F
F
F
T
F
F
T
T
F
T
T
T
F
T
T
T
T
F
F
T
T
F
F
T
T
F
T
T
T
T
T
T
T
T
F
T
F
F
T
T
T
T
T
F
F
T
T
T
T
T
T
T
F
F
F
T
T
T
T
T
T

Now for the fun part; to prove it using inference laws. To briefly describe what I'm doing, there are 2 parts to this proposition. The left part is: [p → (q → r)]  and the right part is: [(p → q) → (p → r)] 
I'll work on the left part first and then the right part.

[p → (q → r)] → [(p → q) → (p → r)] 
[p → (¬q ∨ r)] → [(p → q) → (p → r)] 
[¬p ∨ (¬q ∨ r)] → [(p → q) → (p → r)] 
[¬p ∨ (¬q ∨ r)] → [(¬p ∨ q) → (¬p ∨ r)] 
[¬p ∨ (¬q ∨ r)] → [¬(¬p ∨ q) ∨ (¬p ∨ r)] 
[¬p ∨ (¬q ∨ r)] → [(p ∧ ¬q) ∨ (¬p ∨ r)] 
[¬p ∨ (¬q ∨ r)] → [((p ∧ ¬q) ∨ ¬p) ∨ r)] 
[¬p ∨ (¬q ∨ r)] → [((¬p ∨ p) ∧ (¬p ∨ ¬q)) ∨ r)] 
[¬p ∨ (¬q ∨ r)] → [(T ∧ (¬p ∨ ¬q)) ∨ r)]
[¬p ∨ (¬q ∨ r)] → [(¬p ∨ ¬q) ∨ r)]
[¬p ∨ (¬q ∨ r)] → [¬p ∨ (¬q ∨ r)]


 At this point we see that the left is identical to the right. If we let w = ¬p ∨ (¬q ∨ r), then w → w is True no matter what the Truth value of w is. If w is True then T → T is True; also, if w if False then F → F is also True. But just for the fun of it, lets see if we can get a nice T at the end.


¬[¬p ∨ (¬q ∨ r)] ∨ [¬p ∨ (¬q ∨ r)]
[p ∧ ¬(¬q ∨ r)] ∨ [¬p ∨ (¬q ∨ r)]
[p ∧ (q ∧ ¬r)] ∨ [¬p ∨ (¬q ∨ r)]
[p ∧ (q ∧ ¬r)] ∨ ¬p] ∨ [(¬q ∨ r)]
[(¬p ∨ p) ∧ (¬p ∨ q) ∧ (¬p ∨ ¬r)]] ∨ [(¬q ∨ r)]
[T ∧ (¬p ∨ q) ∧ (¬p ∨ ¬r)]] ∨ [(¬q ∨ r)]
[(¬p ∨ q) ∧ (¬p ∨ ¬r)]] ∨ [(¬q ∨ r)]
[(¬p ∨ q) ∧ (¬p ∨ ¬r)] ∨ ¬q] ∨ r
[(¬q ∨ (¬p ∨ q)) ∧  (¬q ∨ (¬p ∨ ¬r))] ∨ r
[((¬q ∨ ¬p) ∨ (¬q ∨ q)) ∧  (¬q ∨ (¬p ∨ ¬r))] ∨ r
[((¬q ∨ ¬p) ∨ T) ∧  (¬q ∨ (¬p ∨ ¬r))] ∨ r
[T ∧  (¬q ∨ (¬p ∨ ¬r))] ∨ r
(¬q ∨ (¬p ∨ ¬r)) ∨ r
((¬q ∨ ¬p) ∨ (¬q ∨ ¬r)) ∨ r
(r ∨ (¬q ∨ ¬p)) ∨ (r ∨ (¬q ∨ ¬r))
(r ∨ (¬q ∨ ¬p)) ∨ (¬q ∨ (r ∨ ¬r))
(r ∨ (¬q ∨ ¬p)) ∨ (¬q ∨ T)
[r ∨ (¬q ∨ ¬p)] ∨ T
T

Comments

Post a Comment

Popular posts from this blog

Beginner Java Exercise: Sentinel Values and Do-While Loops

In my previous post on while loops, we used a loop-continuation-condition to test the arguments. In this example, we'll loop at a sentinel-controlled loop. The sentinel value is a special input value that tests the condition within the while loop. To jump right to it, we'll test if an int variable is not equal to 0. The data != 0 within the while (data != 0) { ... } is the sentinel-controlled-condition. In the following example, we'll keep adding an integer to itself until the user enters 0. Once the user enters 0, the loop will break and the user will be displayed with the sum of all of the integers that he/she has entered. As you can see from the code above, the code is somewhat redundant. It asks the user to enter an integer twice: Once before the loop begins, and an x amount of times within the loop (until the user enters 0). A better approach would be through a do-while loop. In a do-while loop, you "do" something "while" the condition...
13 comments
Read more

Programming Language Concepts Test Questions/Answers

One of the easiest methods that I use to learn new topics is by creating notes on the subject and then by turning those notes into questions and answers. Remembering answers to questions just seems more natural. I was able to memorize 323 questions and answers in a matter of a couple of days. I wanted to start doing this for some topics that I find pretty interesting. To begin, here are some questions and answers to Programming Language Concepts (PLC). I'm reading your mind right now and the answer is yes, there will be more. 1. Name 3 reasons for studying PLC. - Better understanding of current programming languages - Advancement of computing - Increased capability to express ideas - Increased capability to learn new programming language. - Better understanding of which programming language to choose.  2. Name the 5 programming domains and languages best suited for each. - Scientific (Fortran, ALGOL 60) - Business (COBOL) - AI (Lisp, Scheme, Prolog) - Web (PHP, ...
12 comments
Read more

Creating your own ArrayList in Java

Wanted to show that certain data structures in Java can be created by you. In this example, we'll go ahead and create an ArrayList data structure that has some of the methods that the built in ArrayList class has. We'll create 2 constructors: The default constructor that creates an ArrayList with a default size of 10. Constructor that allows an initial size to be passed to the array. We'll also create a number of methods: void add(Object x);  A method that allows you to place an Object at the end of the ArrayList. void add(int index, Object x);  A method that allows you to place a value at a given location. Object get(int index):  Allows you to retrieve a value of the arrayList array from a given location. int size();  Allows you to get the number of elements currently in the Arraylist. boolean isEmpty();  Tests to see if the Arraylist is empty. boolean isIn(Object x);  A method that sees if a particular object exist in the arrayList. int ...
49 comments
Read more