1
vote
1answer
31 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
0
votes
2answers
36 views

What is the Equivalent formula of $((a\to b) \to ((a \to c) \to (c \to a)))$

Need help to solving a logic. The question is to find an equivalent to the following logic. $((a\to b) \to ((a \to c) \to (c \to a)))$ Thanks in advance for help.
1
vote
1answer
43 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
1
vote
1answer
34 views

How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
2
votes
1answer
111 views

About $\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}$ . . .

Suppose $$\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}.$$ Which of the following is true? Explain your answer. For any $n$, $$\Sigma\cup\{p_n, \neg p_{n+1}\}$$ is complete and ...
-1
votes
1answer
60 views

Quick Truth Table in Logic Problem

Suppose We Have: How can quickly detect how many "1" are in the truth table of above formula? (without drawing Truth Table). i think by using some inference. any idea? we know there are 11 "1"s ...
1
vote
1answer
33 views

Discrete math and rules of inference

I recently did this rules of inference/logic question and the method I used was different from the textbook so I was wondering if my work was correct?
0
votes
1answer
45 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
1
vote
1answer
44 views

Rules of inference: The Rules of Disjunctive Syllogism and Double Negation

I have a question about the use of Double Negation in relation to this problem I found in my textbook examples. Problem: $\;¬(r \land t) \lor u$ $\;r \land t$ Therefore, $u$. In my textbook it ...
0
votes
2answers
54 views

Using DeMorgan’s rule, state the negation of the statement

Using DeMorgan’s rule, state the negation of the statement: “The car is out of gas or the fuel line is plugged.” Let C stand for “The car is out of gas” and let F stand for “the fuel line is ...
1
vote
1answer
41 views

$(A \lor B) \implies (((A \lor B) \implies A) \lor ((A \lor B) \implies B))$?

Is the implication in the title true? I haven't studied logic formally yet, so I can't precisely say what A, B exactly are. Perhaps "predicates in first-order logic"?
0
votes
1answer
35 views

How's my proof?

Prove that not every boolean function is equal to a boolean function constructed by only using $∧$ and $∨$. If p,q = (0,1) (p$∧$q)$∨$q = (0$∧$1)$∨$1 = 1 (p$∧$q)$∨$~q = (0$∧$1)$∨$~1 = 0 Therefore ...
0
votes
1answer
87 views

Can you conclude that A = B if A, B, and C are sets such that…

a. A ∪ C = B ∪ C b. A ∩ C = B ∩ C c. A ∩ C = B ∩ C and A ∪ C = B ∪ C My method of solving this was to convert everything to propositional logic, then to solve it to show that none of the above are ...
0
votes
2answers
119 views

How can I prove [P->(Q->R)] is equivalent to [(P^Q) ->R]

I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have ...
1
vote
2answers
24 views

question about equivalence of boolean statements

Does the function $(p \land q) \lor r$ equal the function $p \land (q \lor r)$? please it would be suitable if in your feedback you will include which algebraic rule for boolean function to follow.. ...
1
vote
1answer
24 views

Is it possible to prove an argument is not satiable with equivalences?

I am trying to prove is this argument: (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) is satiable with equivalence. Is what I said below valid for this? (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) q ∨ (p ∧ ¬p) ...
0
votes
1answer
120 views

Propositional Logic with rules of inference problem.

$$ \begin{array}{l} 1.\>\>\>\> (r ∧ ¬s) ∨ (q ∧ ¬s)\\ 2.\>\>\>\> ¬s → ((p ∧ r) → u)\\ 3.\>\>\>\> u → (s ∧ ¬t)\\ ...
0
votes
1answer
59 views

Rules of Inference…From the following premises, conclude that p → q.

1. (r ∧ ¬s) ∨ (q ∧ ¬s) 2. ¬s → ((p ∧ r) → u) 3. u → (s ∧ ¬t) ----------------------- Prove from the previous arguments. p → q Hey guys, I am really lost, so far I ...
1
vote
1answer
46 views

Equivalence Proof (p ∧ q) ∨ ¬(p → q) ∨ ¬(q ∧ r).

I am trying to prove (p ∧ q) ∨ ¬(p → q) ∨ ¬(q ∧ r) ≡ ¬r ∨ (q → p). So far I have done the following: (p ∧ q) ∨ ¬(¬p ∨ q) ∨ ¬(q ∧ r) Implication Definition (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬q ∨ ¬r) De ...
1
vote
2answers
61 views

How is this disjunctive form found through propositional algebra

I'm learning about disjunctive normal form and the algebra of propositions. The text is Discrete Mathematics with Graph Theory, 3rd Edition by Goodaire and Parmenter (it wasn't highly recommended on ...
0
votes
2answers
35 views

Intro to Discrete Structures $\;\lnot A \rightarrow (A \rightarrow B)$

Im trying to use propositional logic to break this down but i have no clue. i know about the rule that if a wff ends in form ....implies (a implies b), the a can be ...
1
vote
2answers
70 views

How can I show that three statements are not logically equivalent to another?

I am given three premises and a conclusion. The premises are: \begin{gather} p \lor q \\ p \to \mathord{\sim}q \\ p \to r \end{gather} and the conclusion is $$ r $$ I used a truth table and showed ...
4
votes
5answers
153 views

Are $p \to (q \to r)$ and $p \to (q \wedge r)$ logically equivalent?

Is $p \to (q \to r)$ logically equivalent to $p \to (q \wedge r)$? I simplified each one, I got $\neg\, p \vee(q \vee r)$ and $\neg\, p ∨(\neg\, q \wedge r)$ respectively. Not sure if my ...
2
votes
1answer
150 views

How to check the validity of this argument using the rules of inference?

I have this argument : I play basketball and football. If today isn't Saturday, then I play basketball and football. If today is Friday OR today is Saturday, then I don't play football. Therefore, ...
2
votes
4answers
446 views

Satisfiability Problem: Determining Which People To Invite

When planning a party you want to know whom to invite. Among the people you would like to invite are three touchy friends. You know that if Jasmine attends, she will become unhappy if Samir is ...
1
vote
1answer
77 views

Defining what a proposition is is in propositional logic

What is an exact definition of a proposition that we can use to apply to sentences in natural language? Are the following propositions? 1.) "I am calling you a liar." 2.) "4 is the square root of ...
0
votes
1answer
41 views

Nested Quantifiers - Differentiating between $\forall x \forall y$, $\forall x \exists y$, and $\exists x \exists y$

I have a few questions regarding quantifiers which I'm still not clear about. 1) $\forall x \forall y (x^2 + y^2 = 9)$ I believe this is false as x and y could be 2 and results in 8. 2) $\forall x ...
0
votes
1answer
33 views

Write $p \rightarrow \lnot q$ in CNF form with only and ,or and brackets

Write $p \rightarrow \lnot q$ in CNF form with only and, or, and/or brackets How on earth would I even do this? Completely lost! Any help appreciated.
1
vote
2answers
38 views

I have confusion while translating propostions to logical expressions

I have following propositions: p:Grizzly bears have been seen in the area. q:Hiking is safe on the trail. ...
2
votes
1answer
99 views

tautologies and contradictions with $r$

I'm really struggling to understand tautologies and contradictions. I've been able to do $(p \rightarrow q) \leftrightarrow (\lnot q \rightarrow \lnot p)$ and I understand why it is a tautology, ...
3
votes
2answers
114 views

is $p \land (p \lor q)$ a tautology?

I would just like to know whether my work is correct before I continue on with the rest of the questions. $$p \land (p \lor q)$$ $$p \land (\lnot p \rightarrow q)$$ $$(p \land \lnot p) \rightarrow ...
1
vote
1answer
219 views

How to prove these using natural deduction

I'd like to prove the following logical equivalence by using natural deduction: $$(\exists x)(p(x) \implies q) \dashv\vdash (\forall x)(p(x)) \implies q.$$ As far as I'm concerned to show that two ...
2
votes
2answers
1k views

Using DeMorgan's Laws to complement a function

Using DeMorgan's Law, write an expression for the complement of $F$ if: $F(x,y,z) = x(y' + z)$. $F=x'+(y'+x)'$ $F(x,y,z) = xy + x'z + yz'$ $F=(xy)'(x'z)'(yz')'$ $F(w,x,y,z) = xyz' (y'z + x)' + ...
4
votes
2answers
184 views

Natural deduction: $(\neg q \to\neg p)\vdash(p\to q)$ without Modus Tollens

Can anyone help me to obtain this result in natural deduction, without using modus tollens: $$(\neg q \to \neg p) \vdash ( p \to q)$$
1
vote
3answers
426 views

I need to show the validity of the below arguments by using a truth table

I need to show the validity of $P \rightarrow Q$ $P \rightarrow R$ $\therefore P \rightarrow (R \wedge Q)$ Can i just show the truth table for $P \rightarrow Q$ and the truth table for ...
1
vote
1answer
100 views

Discrete math proof issue

This is a question from my discrete math quiz. I was asked to prove there exists a Q(x). I used Disjunctive Syllogism to prove it. I was marked incorrectly because I used two different variables in ...
0
votes
1answer
68 views

Proof methods Discrete Math

Claim: for any integers m and n, if $7m + 5n = 147,\,$ then $m$ is odd or $n$ is odd a) state the converse of the claim b) state the contrapositive of the claim. c) use proof by contrapositive to ...
0
votes
2answers
90 views

Proving that $\{\to, \lnot\}$ is logically complete

Prove that $\{\to,\lnot\}$ is logically complete. It is known that $\{\land, \lor, \lnot\}$ is logically complete.
2
votes
2answers
107 views

Rules of inference proofs

I have the following: Premise: {$p \lor q, q\rightarrow r,p \land s \rightarrow t, \lnot r, \lnot q \rightarrow u \land s$}, conclusion: $t$ I'm having a real hard understanding how to prove the ...
2
votes
2answers
155 views

Translation of sentence into logical proposition

Given the sentence: "You can access the internet only if you are a computer science major or you are not a freshman" and functions: a = you can access the internet b = you are a computer science ...
1
vote
2answers
256 views

Can mathematical induction be used to disprove something?

I saw this to be the rule of inference for mathematical induction : Now consider : as L.H.S. and as R.H.S.. Now if suppose, while trying to prove P(k) -> P(k+1), in the left hand side of ...
0
votes
1answer
1k views

Proving/Disproving Product of two irrational number is irrational

I saw this question where I had to prove/disprove that: Ques. Product of two irrational number is irrational. I tried 'Proof by Contraposition'. Product of two irrational number is irrational. p ...
1
vote
2answers
75 views

Propositional logic problem

Show that [ (p ∨ q) ∧ (p → r) ∧ (q → r) ] → r is a tautology (without a truth table). I am new to this, so I am not quite sure of how some rules can be used. Here is what I have so far: ...
0
votes
1answer
899 views

A Proof relating to the Disjunctive normal form

Here is a problem from Kenneth Rosen's Discrete Mathematics and its Applications, Section 1.3 Suppose that a truth table in $n$ propositional variables is specified. Show that a compound ...
2
votes
1answer
296 views

“Rules of inference” when the last premise is a conditional?

Another very basic Discrete Mathematics homework problem. I don't want the answer as much as I want to understand the question: Problem 7 For each of the following sets of premises, ...
1
vote
4answers
134 views

Writing an expression using logic

Write an expression using letters $\land, \lor, and$ $\neg$ which has the following truth table: $$\begin{array}{ccc|c} P&Q&R&???\\ \hline T&T&T&F\\ T&T&F&T\\ ...
2
votes
2answers
84 views

Are these propositions equivalent?

Statement 1: Maria will find job if she learns mathematics. Statement 2: Maria will find a job unless she does not learn mathematics. I know the answer is probably that these are same, but ...
1
vote
2answers
651 views

Prove logical equivalence

\begin{gather} (p \to q) \equiv (\lnot p \lor q) \\ \lnot(p \land q) \equiv (\lnot p \lor \lnot q) \end{gather} Can these be proven without truth tables?
0
votes
3answers
84 views

Implication review!

I am currently studying for my Discrete Structures final exam, and there is a question I am not sure how to answer... Question is: Consider the following implication. "If i do not debug the ...
1
vote
2answers
810 views

Prove a tautology using truth table

How do I prove $(\lnot p \rightarrow F)\rightarrow (p=T)\;$ using a truth table? (This tautology symbolizes a "proof by contradiction". If p being false leads to a contradiction, then p is true.)