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
31 views

Can the OR function be linearly separated?

I have two questions regarding linear functions and propositional calculus: 1) How do you decide if, for example, the OR function can be linearly separated? The answer is Yes, however I don't know ...
2
votes
1answer
94 views

Predicated needed for proof using structural induction

I have a set, $F$, of boolean formulas defined inductively as follows: $X_{i} \in F, \: \forall i \in \mathbb{N} \: \text{(variables)}\\ A \in F \implies \neg A \in F\\ A, B \in F \implies A \land B ...
1
vote
2answers
52 views

Proof by cases and contradiction. Is this valid?

Say i have a hypothesis of the following form: $P \lor Q$ and a conclusion $\neg A$. I try a proof by contradiction; so I assume $A$. Now what I am trying to do is break the hypothesis into cases, so: ...
1
vote
1answer
41 views

Deduction theorem with undischarged statement

I am reading "Mathematical logic" by Ian chriswell and Hodges and at one point in the text they mention the deductive theorem (page 17) which states; If $\Gamma \cup \left \{ \phi \right \} \vdash ...
0
votes
2answers
73 views

How can I indicate a truth table if its Valid or Invalid?

Construct a truth table for Destructive Dilemma using the general symbolic notation for the rule of inference, T for true value, F for false value. Indicate whether valid or invalid. Is this the ...
5
votes
2answers
75 views

Are there some techniques for checking whether a statement implies another without truth tables?

Are there some techniques for checking whether a statement implies another without truth tables? For example, I was asked whether $P\Longrightarrow P_{1}$ given the following statements: $$P: [p ...
0
votes
1answer
60 views

How to prove a tautology using proof by contradiction?

I am trying to learn proof by contradiction. How would i go about proving that ((A => B) and (C => D)) => ((A => D) or (C => B)) is a tautology, ...
6
votes
2answers
98 views

The logical law of closed systems of sentences

Consider the usual logical connectors $\wedge, \vee, \supset, \neg$ (i.e., "and", "or", material implication, negation) and the "stroke" $/$ defined as $p / q := (\neg p) \vee (\neg q)$. In his book ...
0
votes
1answer
21 views

Prove conjecture using premises

I have three premises with me defined: $(B \land L) \implies A$ $(A \land D) \implies \lnot H$ $\lnot J \implies (D \land \lnot H)$ I need to prove the following conjecture with the help ...
1
vote
6answers
124 views

Why is $P \to Q \equiv \neg P \vee Q$?

By truth table, we know that $P \to Q$ is equivalent to $\neg P \vee Q$. But I'm trying to understand why this work? How can connective "or" be implication. I tried some examples but I still can't ...
2
votes
2answers
45 views

Is the following propositional function well defined?

My question is fairly simple: Is $(P \wedge Q)(x)$ equivalent to $P(x)\wedge Q(x)$? Reason I'm asking, is that when I asked my tutor he said the statements weren't equivalent because if $P(x) = "x\ ...
0
votes
1answer
129 views

Proving a property about logical entailment

I have an intuitive idea that, given some set of formulas $Γ$, and two formulas $A, B \not\in Γ$, $((Γ\cup{A}) \models B)↔(Γ \models (A→B))$. I can rationalize this as, if the left side of the ...
0
votes
1answer
53 views

Is an argument valid simply if its form is valid?

Can I conclude that an argument is valid if its argument form is valid? I realize that a false premise may lead to an incorrect conclusion (which is not what I'm asking). I see a lot of questions ...
1
vote
1answer
70 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
42 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
77 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
52 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
1answer
109 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 ...
1
vote
1answer
43 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
85 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
58 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
183 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
61 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
76 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
109 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
35 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
44 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
23 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
38 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
50 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
71 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
66 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
106 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
153 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
30 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
47 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
36 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
36 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
43 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
20 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
40 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
45 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
87 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
26 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
78 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
52 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$. ...