Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

3
votes
3answers
153 views

Proving using axioms of propositional logic

As part of my upcoming exam in Mathematical Logic we are supposed to be able to prove a given statement using a list of given $axioms$, $M.P.$ and $H.S.$ My question is, how do I approach these kinds ...
2
votes
1answer
68 views

How do I prove the tautology $\vdash((p\rightarrow q)\rightarrow p)\rightarrow p$ using natural deduction?

I'm trying to prove $\vdash((p\rightarrow q)\rightarrow p)\rightarrow p$. The best attempt I can come up with is as follows: $((p\to q)\to p)$ Assumption $p\to q$ Assumption $p$ ...
7
votes
4answers
188 views

Showing $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ {without truth table}

Problem: Show $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ Source: As was noted in the original post, this problem is from Daniel J. Velleman's book ...
4
votes
1answer
63 views

Simplify $(p\land q)\lor(p\land \neg q)$

So I was asked to simplify this statement $S$: $$(p \land q) \lor (p \land \neg q)$$ My understanding is that it needs to have a similar truth table, though I'm not sure if that's exactly right. ...
3
votes
1answer
79 views

Do we actually define implications using an implication itself?

Everything in math stems from definitions. Eg: Let an 'implication' be defined as ... But any such 'let' actually means 'if it be true that'. So what we're really saying is 'If an implication be ...
2
votes
0answers
77 views

Show equivalence of statement $\left(P\rightarrow Q\right) \wedge \left(Q\rightarrow R\right)$ to … [duplicate]

Show that $\left(P\rightarrow Q\right) \wedge \left(Q\rightarrow R\right)$ is equivalent to $\left(P\rightarrow R\right) \wedge \left[\left(P\leftrightarrow Q\right) \vee \left(R\leftrightarrow ...
2
votes
3answers
197 views

Problem solving Logical Equivalence Question

I am working with Logical Equivalence problems as practice and im getting stuck on this question. Can somebody help? Im trying to show that The LHS is equivalent to the RHS (¬P ∧ ¬R) ∨ (P ∧ ¬Q ∧ ¬R) ...
0
votes
0answers
37 views

Performing arithmetical operations (with binary numbers) using propositional logic

Clarifying some terms. By arithmetical operations I mean the four basic operations of addition, subtraction, multiplication and division. By binary numbers I mean numbers in the binary system. By ...
1
vote
1answer
46 views

Prove $R$ follows from premises $(\lnot R\rightarrow\lnot Q),\;(P\lor Q,),\; (\lnot(P \lor T))$

I'm preparing for an exam and we weren't given an answer sheet. I'd like to know if my reasoning for the given conclusion is correct? Premises: $(\lnot R) \rightarrow (\lnot Q),\;\; (P \lor Q),\;\; ...
2
votes
1answer
34 views

Consider the statement and decide which of the following implies that this statement is true.

Consider the statement: If Bill takes Sam to the concert, then Sam will take Bill to dinner. Which of the following implies that this statement is true. $\\$ a. Sam takes Bill to dinner only if ...
0
votes
1answer
55 views

Using rules of inference with quantified statements

Use rules of inference to show that (a) $ ∀x (R(x) → (S(x) ∨ Q(x))$ $∃x (¬S(x))$ $ ∃x (R(x) → Q(x) )$ I'm kinda lost at what to do... I can start but don't know what to do afterwards 1) $R(a) ...
0
votes
1answer
53 views

Immediate consequence in Gödels incompleteness paper

In the famous paper, “On Formally Undecidable Propositions of PM”, $c$ is defined as the immediate consequence of $a$ and $b$ if $a$ is the formula $\lnot b \lor c$. How does this relate to the ...
4
votes
1answer
82 views

Formal proof of $P\to Q, (P\to Q)\to (T\to S), \neg Q, P\lor T\vdash S$

This is an example exam question that I'm wondering if I did right? We weren't given an answer key, so I'm checking to make sure I'm comprehending the material and if my answer is correct? Premises: ...
0
votes
2answers
75 views

help verifying my answer for this“ premise-conclusion” question

For each of the premise-conclusion pairs below, give a valid step-by-step argument (proof) along with the name of the inference rule used in each step. (a) Premise: {¬p ∨ q → r, s ∨ ¬q, ¬t, p → t, ...
2
votes
2answers
114 views

Is there a name for: (p => q) => ((p and r) => q)?

Is there a name for the following inference rule?: If (p => q), then we infer [for all r]: (p and r) => q If so, what is it? I use the above inference ...
2
votes
1answer
45 views

Express $(A\to B)\land((C\land B)\to A)$ using biconditional

Is there a way to express the formula $(A\to B)\land((C\land B)\to A)$ as a biconditional, i.e. as a statement of the form $\phi\leftrightarrow\psi$ for some expressions $\phi(A,C)$, $\psi(B,C)$? Of ...
0
votes
2answers
215 views

Prove using a proof sequence and justify each step

Prove using a proof sequence that the argument is valid [ A --> (B ∨ C) ] ∧ B' ∧ C' --> A' I'm having some trouble figuring the proof out here. Here is what I have so far. Is this on the right ...
2
votes
0answers
42 views

How can i solved this using fitch notation?

I have a little problem that is proof this following statement using fitch notation, can anyone help me out? :) |= (t → s) ∧ ¬((s → q) → (t → q)) Thanks in advance.
1
vote
2answers
48 views

Are the following contradictions?

I have the following: $p\to (q\land p)$ $p\to \neg (q\land p)$ I am asked if they are contradictions, can someone explain what that means exactly. I did a truth table for both, and if ...
1
vote
1answer
38 views

Logic - Simplifying a propositional logic expression

So my teacher was showing us an example in class and then blasted through it during the last minutes of the class. He does not respond to his emails outside of his office hours, so I was wondering if ...
0
votes
1answer
40 views

Conjunctive Normal Form Conversion

The question is to turn the following formula into Conjunctive Normal Form: $\rm \neg [(p \vee q) \wedge (r \to s)] \to p \wedge \neg q \wedge \neg s$ I have come up to here: $\rm \neg [(p ...
3
votes
1answer
56 views

Tautology - First Order Logic

I have a question in my exam practice, to determine if the following statement is a tautology, in First Order Logic: I think it is a tautology, but am I correct? In my course the proffesor told us ...
0
votes
1answer
22 views

How do I notate a proposition with multiple conditions?

Lets's say I have the predicates: F(x) means x is even G(x) means x is a prime number and we take the universe of discourse to be the set of natural numbers N = {1,2,3,...} How do I notate a ...
1
vote
0answers
28 views

Translation into the propositional logic

How could the following sentence be translated into the propositional logic? Since I am here I talk to you. Do I have to use implication like p -> q?
0
votes
3answers
45 views

$p\land\neg q\to r, \neg r, p ⊢ q$ -natural deduction

I have the following: $$p\land\neg q\to r, \neg r, p ⊢ q$$ I know that my attempt is incorrect, but I will show it anyways: Step 1) $p\land\neg q\to r$ ----premise Step 2) $\neg r$ -----premise ...
2
votes
1answer
51 views

$⊢p \land q \to (p\to q)$ - Natural deduction proof confusion

I have the following: $$⊢p \land q \to (p\to q)$$ I'm having a difficult time trying to figure out where to begin. I believe that I am supposed to assume p and ...
2
votes
2answers
89 views

If $s_{1}\Longleftrightarrow s_{2}$ then $s_{1}\leftrightarrow s_{2}$ is a tautology?

I see that it's not always the case for $s_{1}\leftrightarrow s_{2}$ is a tautology. As if I have $s_{1}:p$ and $s_{2}:q$, I have the following truth table: $$ \begin{array}{c|c|c|c|c|c|c} p & q ...
1
vote
1answer
27 views

Can there be a vacuous tautological consequence $F\vDash F$?

Can there be a vacuous tautological consequence $F\vDash F$? Since $α⊨φ \iff ⊨α→φ$ then is: $(k∧¬k)⊨(p∧¬p)$ for example considered a tautological consequence?
1
vote
3answers
79 views

Need Help with Propositional Logic

I am stuck with this proof. I am trying to use deduction (or induction I think) to prove for a tautology with logic laws like De Morgan's, distributive , and implication law etc. Note: I am not ...
-1
votes
1answer
56 views

Finding a formula in intuitionist logic [closed]

I am looking for a formula which is true semantically but not syntactically in propositional intuitionist logic. Does it exist? If yes what's that? Thanks for your help.
1
vote
1answer
17 views

Proving $a\equiv b \iff F_a=F_b$, $F_a=\{c\mid a\vDash c\}$

Let $a$ be a proposition (atomic or not), and let $F_a=\{c\mid a\vDash c\}$ is the set of all the propositions that are tautological consequence of $a$. Prove that $a\equiv b \iff F_a=F_b$. ...
1
vote
1answer
74 views

Modus tollens - Negations on the implication

This is likely a basic question however based on my textbook definition of Modus tollens it looks like this: $$\neg q$$ $$\frac{(p \implies q)}{\neg p}$$ I however have something that looks like ...
5
votes
2answers
195 views

Why isn't Modus Ponens valid here

I have the following: $(\neg A \lor B) \rightarrow (\neg A \lor B) \\ (\neg A \lor B) \\ \vdash \neg A \lor B $ And in my mind this seems like a legitimate use of the Modus Ponens rule. But the ...
1
vote
3answers
203 views

When proving the Hypothetical Syllogism inference rule, why must you assume that p is true?

I recently started learning Discrete Maths and currently studying rules of inference. I was looking at a proof of Hypothetical Syllogism, aka: P→QQ→R∴ P→R and I came across this proof of the ...
0
votes
2answers
63 views

Prove/disprove if $a\vee b \Rightarrow c$ then $a\Rightarrow c$ or $b\Rightarrow c$ and vice versa

$a,b,c$ are statements, $\Rightarrow$ is a tautological consequence (not a logical implication and it's not a proposition). Prove/disprove: if $a\vee b \Rightarrow c$ then ...
0
votes
1answer
169 views

Disjunctive normal form (BOTH dnf and cnf) example help

T or ( not x and y ) or ( x and y ) In class we went over examples of how many things can be both DNF and CNF... eg. (not z) or y can be thought of as both (not z) or y .... dnf ((not z) or ...
1
vote
2answers
101 views

Prove/disprove if $a,b\Rightarrow c$ then $(a\Rightarrow c) \vee (b\Rightarrow c)$ and vice versa

Let $a,b,c$ be statements, $\Rightarrow$ is a tautological consequence. Prove/disprove: if $a, b\Rightarrow c$ then is it necessarily $a\Rightarrow c$ or $b\Rightarrow c$ ? if ...
0
votes
1answer
114 views

equivalence laws example proof

Problem taken from here. Use Logical Equivalences to prove that $[(p \land \lnot(\lnot p \lor q)) \lor (p \land q)] \implies p$ is a tautology. implication law... $\lnot[(p \land \lnot(\lnot p ...
0
votes
1answer
80 views

How to prove this distributive law using natural deduction

$(q \lor r)\wedge p\vdash(q\wedge p)\lor (r\wedge p)$ After making the first assumption and splitting it up using ∧-elimination, I get stuck. Can anyone help?
0
votes
2answers
56 views

Propositional Logic - Exactly what does ~ (negation) mean

Let's say p is a statement. Is ~p (negation of p) just opposite of p or is it anything but p. For example, let's say p = "None of the basketball players are blond" Without just adding a 'not' in ...
5
votes
5answers
123 views

How can it be that $(P \rightarrow Q) \vee (Q \rightarrow P)$ is a tautology?

I consider $(P \rightarrow Q) \vee (Q \rightarrow P)$, that is $(\neg P \vee Q) \vee (\neg Q \vee P)$ and so $\neg P \vee Q \vee \neg Q \vee P$, which is a tautology. It seems strange to me that, ...
2
votes
1answer
46 views

Logic Invalidity

I'm having trouble with a problem in Propositional Logic Using induction I am supposed to show that if a well formed formula (wff) X has no repetitions of sentence letters then X is invalid. The hint ...
3
votes
1answer
225 views

Online tools for checking validity of classical, intuitionistic, … logic formulas?

What online tools are available, where one can enter a formula of (first order) propositional or predicate logic, and have it check whether it is valid classically, intuitionistically, or even ...
1
vote
3answers
64 views

Proving that $\{p\to q, p\to \neg q\}\Rightarrow\neg p$

Prove the following: $\{p\to q, p\to \neg q\}\Rightarrow\neg p$, that is, prove that $\neg p$ is a tautological consequence of $\{p\to q, p\to \neg q\}$ (Note: I write $0,1$ instead of $F,T$.) ...
1
vote
1answer
64 views

Is it valid to make an assumption that directly contradicts a given premise?

Is it valid to make an assumption that directly contradicts a given premise? For example, if I want to deduct the proposition $$¬(p→q) ⊢ p∧¬q$$ I'd like to assume $p→q$, so I can falsify things ...
4
votes
3answers
1k views

How to express the statement “not all rainy days are cold” using predicate logic?

I am trying to figure out how to express the sentence “not all rainy days are cold” using predicate logic. This is actually a multiple-choice exercise where the choices are as follows: (A) $\forall ...
0
votes
2answers
87 views

Proving equivalency using boolean algebra laws of logic

I have a question on my exam papers relating to proving equivalences using the laws of logic, but I'm not sure how to work it out as I don't have the solution paper. Can someone explain to me the ...
0
votes
2answers
39 views

Principle of propositional congruence

Let $\varphi$ be a propositional formula, defined as a formula containing propositional symbols and connectives only, and let $\psi,\chi$ be propositions. I read the following principle of ...
2
votes
3answers
97 views

Propositional Logic Tautology Proof

I have question about a proposition that I need to prove is a tautology: $((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ I have tried negating the first large bracket, ...
5
votes
2answers
56 views

Propositional Logic Help

I need to prove that $(\neg p \wedge (p \vee q)) \rightarrow q $ is a tautology using Laws of Logic (not truth tables). This is what I tried: $\equiv (( \neg p \wedge p) \vee (\neg p \wedge q)) ...