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

Laravel 6.x with React and react-router

This will get you started on getting your first React/Laravel application deployed to your server. We'll cover everything from installation to deployment. Start by reading the installation instructions on  https://laravel.com/docs/6.x#installing-laravel . We'll cover those details below. Setting Up Laravel Check that you have the latest version of PHP installed on your computer.  It must be >= 7.2.0. Open terminal to get the Laravel installation tool. Type in composer global require laravel/installer Type in laravel to verify installation. Navigate to a directory on your computer where you want to install your project on your terminal. Run the following command: laravel new project_name (replace project_name with your project name). Once complete, cd into your new project. Type the following command: php artisan serve. You'll get a message like the following if it's running successfully: Laravel development server started: http://127.0.0.1:8000 ...
58 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

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