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)

1
vote
0answers
18 views

Logical implication and valid arguments question

The following is a valid argument: $[[p \lor (q\lor r)]\land \neg q] \rightarrow (p\lor r)$. Determine the rows of the table crucial for assessing the validity of the argument and which rows can be ...
0
votes
0answers
24 views

Completeness of a set of propositional formulas

A set $\sum$ of formulas in propositional logic is complete if for each propositional formula $\phi$ either $\sum \vdash \phi$ or $\sum \vdash \neg \phi$. Clearly every inconsistent set of formulas ...
0
votes
0answers
37 views

Glivenko's theorem for propositional logic: $\neg\neg A, \neg\neg(A \rightarrow B) \vdash \neg\neg B$. [duplicate]

In proving Glivenko's theorem for propositional logic I have found myself not able to prove the following: $\neg\neg A, \neg\neg(A \rightarrow B) \vdash \neg\neg B$. The only inference rule I have is ...
0
votes
1answer
31 views

Proving De Morgan's Law with Natural Deduction

Here is my attempt, but I'm really not sure if I've done it right; as I'm just about getting the hang of Natural Deduction technique. Have I done it correctly? If not, where did I make errors and ...
1
vote
0answers
39 views

Dual formula in propositional logic

There's something I don't understand in my course on propositional logic. In the case of x being a variable, the definition of its dual is x* = x. Right. However, further in the course, there's a ...
1
vote
0answers
52 views

Finding a formula for the number of equivalence classes using $m$ variables and $\rightarrow$

I need to find a formula for the number $n_m$ of equivalence classes of the set of propositional logical formulas only containing the propositional variables $p_0,...,p_m$ and only using the ...
0
votes
0answers
18 views

Prove, by induction on complexity, that, for every s $\in$ $\bar{S}$, s $\models$ t. [on hold]

Let S be a set of propositional terms and let t be a propositional term such that, for every s $\in$ S, s $\models$ t. Let $\bar{S}$ be the set of all propositional terms which can be constructed from ...
1
vote
1answer
33 views

Proof of equality using basic axioms

I'm supposed to prove equivalence associativity using propositional logic axioms. My teacher insists that I use mathematical symbols. Half of the proof is given and I am to derive the second half. ...
3
votes
3answers
58 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
44 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$ ...
0
votes
0answers
26 views

Prove that $(B ∧ ¬I) \supset C,¬C ∧¬I\vdash \neg B$ [closed]

$(B ∧ ¬I) \supset C,¬C ∧¬I\therefore \neg B$ Is this valid? Show me with unsigned tree please.
11
votes
3answers
135 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
60 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
71 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
76 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
2answers
57 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
27 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
43 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
18 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
22 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
48 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
0answers
47 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
50 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
101 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
44 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 ...
1
vote
2answers
97 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 ...
0
votes
2answers
43 views

Logic and Inference Problems [closed]

if suppose $r \to s$ and $ (p \wedge q) \vee r$ is True, which of the following can not be infere? 1) $ p \vee s $ 2) $ q \vee s $ 3) $ p \vee q $ 4) all of the above the book shotly wrote (3) is ...
2
votes
0answers
26 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
45 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
26 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
24 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 ...
2
votes
1answer
26 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
19 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
27 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
33 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
36 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
81 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
25 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
69 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 ...
0
votes
1answer
47 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
44 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
158 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
44 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
55 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
33 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
89 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
42 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
34 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
47 views

Prove that $(P → Q) → (¬Q → ¬P) $ is a tautology [closed]

Prove that $(P → Q) → (¬Q → ¬P)$ is a tautology without using a truth table.