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
52 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 ...
1
vote
2answers
35 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
23 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
23 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
64 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
43 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
41 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
57 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
34 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
58 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
144 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
103 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
381 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
65 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
32 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
29 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
36 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
87 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
106 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
192 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
912 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
167 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
234 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
91 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
63 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
89 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
95 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
95 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
212 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
69 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
832 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
247 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
123 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
79 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
383 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
78 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
706 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.)
4
votes
2answers
396 views

Is `1+101=110` a proposition?

There is a question in a book is: if 1+101=110 is a proposition or not. The author said it's not a proposition, since it's true if the numbers are binaries, is ...
10
votes
2answers
339 views

What is the converse of this statement and is it true?

If $a$ and $b$ are relatively prime, $a\mid c$ and $b\mid c$, then $(ab)\mid c$. I am lost. Would the converse be "If $(ab)\mid c$, then $a$ and $b$ are relatively prime and $a\mid c$ and $b\mid c$" ...
2
votes
2answers
315 views

Sodoku Puzzles and Propositional Logic

I am currently reading about how to solve Sudoku puzzles using propositional logic. More specific, they use the compound statement $\bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9}~p(i,j,n)$, ...
5
votes
1answer
231 views

What are a list of helpful boolean identities for solving boolean functions?

For instance, things like $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ is a very helpful formula to know, as is $P \Rightarrow Q \equiv \lnot P \lor Q$ is another helpful ...
4
votes
3answers
108 views

How does this textbook go from this step to the next in proving this?

Here's the picture of the question: How does it go from p v ~q to ~p -> ~q?
2
votes
2answers
284 views

Rewriting Conditionals In Their Well Known Form

The question is, "Write each of these statements in the form “if p, then q” in English. [Hint:Refer to the list of common ways to express conditional statements.] a) It snows whenever the wind ...
2
votes
3answers
239 views

Writing Propositions With Propositional Variables

The puzzle I am working on is: "Let $p$, $q$, and $r$ be the propositions $p$: Grizzly bears have been seen in the area. $q$: Hiking is safe on the trail. $r$: Berries are ripe along the trail. ...
2
votes
1answer
186 views

Transcribing Propositions In English To The Language Of Logic

The question I am working on is: Let $p$ and$q$ be the propositions $p$:It is below freezing. $q$:It is snowing. Write these propositions using $p$ and $q$ and logical connectives (including ...
1
vote
1answer
246 views

Determine Consistency Of System Specifications

I am looking at an example problem in my text: "Determine whether these system specifications are consistent: 'The diagnostic message is stored in the buffer or it is re-transmitted.' 'The ...
2
votes
1answer
1k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
4
votes
3answers
191 views

Negating “Zach blocks e-mails and texts from Jennifer”

I am reviewing some basic propositional logic. The question that I have come across that has given some confusion is Zach blocks e-mails and texts from Jennifer where I am asked to find the negation ...