Logical Operators and Truth Tables

1.
a.
p q p OR q p ↓q
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
b.
p q p OR q p ↓q ( p ↓ q)↓( p ↓ q)
0 0 0 1 1
0 1 1 0 0
1 0 1 0 0
1 1 1 0 0
Observation: There is no change in the results. Whether we compute the function one time or
recursively, it does not change the results.
c.
We know that the NOT logic, i.e., negation has only one input. If we short both the inputs of
NOR logic, we result in the implementation of NEGATION.
p q f = p ↓ q
0 0 1
0 1 Invalid case (since both the
inputs can have only same
value)
1 0 Invalid case (since both the
inputs can have only same
value)
1 1 0
We can notice from the above truth table that the NOR logic behaves as the NOT logic.
If we apply the NOR logic on the inverted inputs of p and q, it behaves as the AND logic.
p q ~p ~q g= p ↓ q
0 0 1 1 0
0 1 1 0 0
1 0 0 1 0
1 1 0 0 1

From the above truth table, the AND logic is implemented using the NOR logic.
2.
P(x): x is connected to the network
Q(x): x has at least 100 terabytes of storage
a.
( P ( x ) ∧ Q ( x ) )
b.
P ( x ) ∧ Q ( x )
c.
P ( x ) ∨ Q ( x )
3.
P ( x , y ) : x2= y
a.
∃ x P(6 , x)
P ( 6 , x ) ⟹ 62=x
x=36
The truth table of this preposition will be a tautology.
b.
∃ x P ( x , 6 )
P ( x , 6 ) ⟹ x2=6
There exists no such whole number whose square is 6. Hence this statement is false.
c.
∀ x ∃ yP( x , y)
P ( x , y ) ⟹ x2= y
This statement is true as the square of a whole number is always a whole number.
d.
∃ y ∀ xP( x , y)
Same as part (c)
4.
a.

Let n2=4 mbe true
n= √ 4 m
n=2 √m
It is not necessary that n is the multiple of 4.
b.
Let n3 =2 m
n=3
√2m
Hence this statement is not always true.
5.
a.
A− ( B+ C ) +(B ∪ C)
b.
( A ∩ B ) + ( B ∩C ) + ( C ∩ A )−2( A ∩ B ∩C)
c.
U − ( A ∩ B ) + ( B ∩ C ) + ( C ∩ A ) −2(A ∩B ∩C )
6.
It is true that if a relation is symmetric and transitive, it must be reflexive.
Example:
Let U = { a , b , c }
R={( a , b ) , ( b , a ) , ( a , a ) ,( b ,b)}
Also, in a relation R if
pRq ,this meansby symmetricity , qRpis aso true .∧by transitivity , pRpis also true .
¿ every element is reflexive ¿ itself . So this statement is true .
7.
In the given table, only source nodes are mentioned and the destination nodes are missing.
We can not find the correct graph with the missing information.
8.
Let the number of vertices be x
No. of edges in the graph = 10
Degrees: 4*2, 3*(x-2)