Answer to Question #262477 in Discrete Mathematics for Qasim

Question

Write the following logical arguments as predicate expressions, defining the predicates used and domains of

variables. For each argument, mention the inference rules used in each step. [6 marks]

a) “Asim, a student in this class, owns a Honda bike. Everyone who owns a Honda bike has gotten at least

one traffic violation challan. Therefore, someone in this class has gotten a traffic violation challan.”

b) “Every student who has taken discrete structures course can take algorithms course. Haris, Nouman, and

Azhar, has taken discrete structures course. Therefore, all five roommates can take algorithms course.”

c) “All movies produced by John Sayles are wonderful. John Sayles produced a movie about coal miners.

Therefore, there is a wonderful movie about coal miners.”

d) “There is someone in this class who has been to Saudi Arabia. Everyone who goes to Saudi Arabia

performs Umrah. Therefore, someone in this class has performed Umrah.”

Answer 1

a)

U- set of allpeople

C- students of this class

P:U->{0,1}- predicat,P(X)=1~man X$\in$ U has Honda bike.

Q:U->{0,1}-predicat,Q(X)=1~ man X has gotten at least one traffic violation challen.

Given that $P(Asim),\forall(X\in U)(P(X)->Q(X))$

From specialization rule we have $P(Asim),P(Asim)->Q(Asim)$

Therefore by modus ponens rule Q(Asim), but $Asim\in C$

By definition $\exist$ we have $\exist (X\in C) Q(X).$

b)

U- set of all students.

P:U->{0,1}-predicat, P(X)~X has taken discret structure course

Q:U->{0,1}-predicat ,Q(X)~ X can take algorithm course.

C- set of five roommates, |C|=5,

Statement is

$P(Azhar),P(Haris),P(Nouman), \forall(X\in U)(P(X)->Q(X))->\forall(Y\in C)Q(Y)$

is not true because there is such interpretation that left part true but right part is false. Evidently C\{Azhar,Haris,Nouman}$\ne\empty$ .

Let $a\in C$ \{Azhar,Haris,Nouman},in interpretation we assume P(a)=Q(a)=0,

P(Azhar)=P(Haris)=P(Nouman)=Q(Azhar)Q=(Haris)=Q(Nouman)=1

Then $\forall(Y\in C)Q(Y)=0$ and $P(a)->Q(a)=\overline{P(a)}\lor Q(a)=\overline 0 \lor 1=1$ , therefore

$P(Azhar),P(Haris),P(Nouman), \forall(X\in U)(P(X)->Q(X))->\forall(Y\in C)Q(Y)=1$

Thus statement is not true.

c)

P(X)- movie X is wonderful.

Q(X) movie X produced by John Sayles.

R(X) movie X is about coal miners.

U-set of all movies.

Statement is:

$\forall(X\in U)(Q(X)\rarr P(X)),\space \exist(X\in U)(Q(X)\land R(X))\rarr \\ \exist(X\in U)(R(X)\land P(X))$

Proof:

$\exist(X\in U)(Q(X)\land R(X))\implies Q(a)\land R(a)$

concretization;

$\forall(X\in U)(Q(X)\rarr P(X))\implies Q(a)\rarr P(a)$

spesialization

$Q(a)\land R(a)\implies Q(a)$

conjuction rule

$Q(a),Q(a)\rarr P(a)\implies P(a)$

modus ponens

$Q(a)\land R(a)\implies R(a)$

conjuction rule

$P(a),R(a)\implies P(a)\land R(a)$

build conjuction rule

$P(a)\land R(a)\implies \exist(X\in U)(R(X)\land P(X))$

build existence rule

d)

P(X)~ X has been to Saudi Arabia

Q(X)~X performs Umrah

U- set of all people

C- this class

Statement:

$\exist (X\in C)P(X),\space \forall(X\in U)(P(X)\rarr Q(X))\implies \exist(X\in C)Q(X)$

Proof:

a$\in$ C, P(a)- conctetization'

P(a)->Q(a)- specialization;

$P(a),P(a)\rarr Q(a)\implies Q(a)$

modus ponens

$Q(a)\implies \exist(X\in C)Q(X)$

definition of $\exist$