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
5answers
208 views

Question on logical inferences

The instruction of this question is: Encode the following arguments and show whether they are valid or not. If not valid give countermodels i.e., truth assignments to the propositions which ...
2
votes
5answers
244 views

Is the propositional set infinitely countable

Recently I'm learning logic. Here is the definition from the book "Logic For Computer Science": A countable set PS of proposition symbols: P0,P1,P2... The set PROP of propositions is the smallest set ...
6
votes
8answers
598 views

General form of a proof that $ab=0 \implies a=0 \lor b=0$

When proving that $ab = 0 \implies a = 0 \,\mbox{ or }\,b = 0$ for members $a$ and $b$ of a field, I used an argument like Suppose $ab = 0$ and $a \ne 0$ ... then $b = 0$. Now suppose $ab = 0$ and ...
4
votes
1answer
177 views

“Sum” over logical and?

Given a continuous sequence of integers $(a, a+1, a+2, \dots, b)$ I want to write: $P_a \wedge P_{a+1} \wedge P_{a+2} \wedge \dots \wedge P_b$ Where $P_i$ is some logical statement parametrized by ...
2
votes
3answers
308 views

Find an equivalent to $(P \lor Q) \land (P \to R) \land (Q \to S)$

I need some help regarding solving a logic. The question is to find an equivalent to the following logic. $$(P \lor Q) \land (P \to R) \land (Q \to S)$$ The choices are (a) $S \land R$ (b) $S ...
1
vote
1answer
3k views

Finding Satisfiability, Unsatisfiability and Valid well formed formula

I have a confusion regarding how to check whether a wff is satisfiable, unsatisfiable and valid. As far as I understood, valid means the truth table must be a tautology, otherwise it is not a valid ...
4
votes
2answers
226 views

Is there notation for “some two of the three statements are true”?

There are three propositions A, B, C and another condition "some two of these propositions are true and the third one is false", or, in other words, "exactly 2 of 3 propositions are true". Using truth ...
5
votes
3answers
2k views

Express logic puzzles with proposition calculus notation

I’m trying to solve a logic puzzle that goes like this: The police have three suspects for the murder of Mr. Cooper: Mr. Smith, Mr. Jones, and Mr. Williams. Smith, Jones, and Williams each declare ...
4
votes
4answers
3k views

What is the name of the logical puzzle, where one always lies and another always tells the truth?

So i was solving exercises in propositional logic lately and stumbled upon a puzzle, that goes like this: Each inhabitant of a remote village always tells the truth or always lies. A villager will ...
0
votes
1answer
117 views

Converting a Proposition to DNF using proof systems

I have been attempting to convent a prop to DNF using a group of common rules, i have applied them all but i think i should be able to get it smaller, This is what I've got so far. Thanks! $$(p \wedge ...
3
votes
2answers
720 views

Formation sequence for a logic formula

I will start with some definitions from An Introduction to Mathematical Logic and Type Theory: To Truth through Proof by Peter B. Andrews then give the exercise that I am working along with my attempt ...
0
votes
1answer
245 views

Request for Help with Predicate Logic Proof

Given the premises in lines 1 and 2, I need to prove that $(\forall x)(\exists y)(Cx \rightarrow Axy)$. $(\exists x)(\forall y)Ayx \lor (\forall x)(\forall y)Bxy$ $(\exists x)(\forall y)(Cy ...
1
vote
3answers
174 views

Predicate Calculus with Sets - Question about use of an axiom

Greets again StackExchange, I am watching an online lecture, and I believe that my instructor has misused an axiom. Is my concern warranted? $$\begin{align*} \text{Given:}& {P \subseteq (Q \cap ...
2
votes
1answer
259 views

Multiple variables for a logical expression?

I wanted to know if what I did is even on the correct path for how this question is worded. How can you have two variables when it's dealing with a single unhappy person? I'm guessing the third way ...
2
votes
2answers
253 views

Written as disjuctions, conjunctions and negations?

With a domain from -2 to 2 I'm trying to write the following using disjunctions conjunctions and nagations. I'm not sure how correct I am and wanted to know if I did them correct? Could someone help ...
1
vote
2answers
316 views

Prove this argument is valid: (~N v (~B*D), ~C --> ~D therefore ~(~C*N))

Prove the following argument is valid (and provide reasons): ~N v (~B*D) ~C --> ~D therefore ~(~C*N) Our work (so far): ~N v (~B*D) ~C --> ~D therefore ~(~C*N) D-->C (contrapositive of 2) ~N v ...
0
votes
1answer
244 views

Show that “likely” is not truth functional

Truth Functional (TF): Has a true/false value which can be completely determined by the truthfulness/falsefullness (?) of the input's values (got that?). Question: Show that "It is likely that __" is ...
2
votes
1answer
283 views

Lindenbaum Algebras

After reading this page, I still have some questions about Lindenbaum algebras. Assume that the scope is a propositional language with a denumerable set X of propositonal variables. In that case, ...
2
votes
1answer
154 views

Proving an implication by proving its dual

My textbook "Discrete and Combinatorial Mathematics, an Applied Introduction" by Ralph P. Grimaldi contains the following definition: Let $s$ be a statement. If $s$ contains no logical connectives ...
11
votes
3answers
606 views

In axiomatization of propositional logic, why can uniform substitution be applied only to axioms?

I'm reading an introductory book about mathematical logic for Computation (just for reference, the book is "Lógica para Computação", by Corrêa da Silva, Finger & Melo), and would like to ask a ...
0
votes
1answer
63 views

Logic - proving that if a predicate is provable then another is provable

I am asked to prove that $$K \vdash (a \rightarrow \exists x \beta ) \implies K\vdash \alpha \rightarrow \beta[t/x]$$ is true using deduction. I've failed to prove this and suspect there is an error ...
0
votes
1answer
324 views

Models of propositional logic

Define a theory of propositional calculus as the set $T$ of axioms (expressed in propositional calculus) and a set of valid symbols. What I would like to see are some examples of theories in ...
3
votes
2answers
168 views

Is the set of self-dual connectives incomplete?

A $n$-ary connective $\$$ is called self-dual if $f_\$(x_1^*, \ldots , x_n^*) = (f_\$(x_1, \ldots , x_n))^*$ where $0^* = 1$ and $1^* = 0$. How to show that the set of such self-dual connectives ...
3
votes
1answer
74 views

Chains in the Lindenbaum algebra

What is the easiest example of an infinite chain in a Lindenbaum algebra for the propositional calculus? Does there exist an infinite antichain in a Lindenbaum algebra?
-1
votes
2answers
291 views

Aristotelian syllogisms in modern mathematics?

Somewhere (?) in the writings of Gian-Carlo Rota, I recall a statement that old-fashioned Aristotelean syllogisms are not used in modern mathematics. I know of one gaudy counterexample, and wondered ...
1
vote
1answer
198 views

Logic translation involving the existential quantifier and “such that”

A: "There exists an integer greater than 5 such that it is less than 10" B: "There exists an integer such that it is greater than 5 and less than 10." C: "There exists an integer less ...
2
votes
1answer
174 views

define simultaneous substitution recursively

Can you help me with my approach to the following task: Define simultaneous substitution $\phi[\psi_1,...,\psi_k/p_1,...,p_k]$ recursively. Usually we have recursive definitions about formulas, but ...
0
votes
1answer
231 views

propositional logic - substitution

Prove: $\varphi_1 =\!\mathrel|\mathrel|\!= \varphi_2 \implies \varphi_1[\psi/p] =\!\mathrel|\mathrel|\!= \varphi_2[\psi/p]$. We've proven that $\varphi_1 =\!\mathrel|\mathrel|\!= \varphi_2 \implies ...
1
vote
1answer
222 views

Confusion about proof that first order logic without equality is not contradictory

I am having a problem understanding a proof from the field of mathematical logic. Seems like my brain cannot digest concepts from logic very well. I will quickly define some terminology and then ...
1
vote
2answers
145 views

How to prove $((Q \wedge ¬P) \vee (Q \wedge P)) = Q$

I cannot see any steps to this problem! Surely the answer is obvious? Is there a particular law which is used to make this statement? $$((Q \wedge ¬P) \vee (Q \wedge P)) = Q$$
5
votes
4answers
589 views

What is a constructive proof of $\lnot\lnot(P\vee\lnot P)$?

Glivenko's theorem says that $\lnot\lnot P$ is a theorem of intuitionistic logic whenever $P$ is a theorem of classical logic. Is it closely related to the so-called Gödel–Gentzen negative translation ...
3
votes
1answer
76 views

How to show that $\mathrm{Cn}(\mathrm{Cn}(A)) = \mathrm{Cn}(A)$?

How to show in propositional logic, that $\mathrm{Cn}(\mathrm{Cn}(A)) = \mathrm{Cn}(A)$? I thought of first showing $\mathrm{Cn}(\mathrm{Cn}(A)) \subseteq \mathrm{Cn}(A)$ and then ...
0
votes
2answers
2k views

I want a clear explanation for the Principle of Strong Mathematical Induction

I understood the Principle of Mathematical Induction. I know how to make a recursive definition. But I am stuck with how the "Principle of Strong Mathematical Induction (- the Alternative Form)" ...
0
votes
1answer
153 views

rank of subformulae

How to show that the rank of a strict subformulae is strictly less than the rank of the formula in propositional logic? I can "see" that it is true, but how to strictly show it? I don't now how to ...
1
vote
2answers
257 views

Predicate Logic Argument Validity

My question is whether or not the following is a validly structured argument: (P→T)→Q Q → ¬Q ∴ P I'm getting hung up on the Q→¬Q part by itself as a premise, it doesn't seem like that is ...
0
votes
3answers
141 views

Logical Equivalance

Determine whether the following pairs of statements are logically equivalent or not. Give a reason. (i) $p \to (q \to r)$ and $(p \to q) \to r$ (ii) $p \to (q \to r)$ and $q \to (p \to ...
3
votes
2answers
324 views

Propositional Calculus: Compactness implies Completeness?

Is there a quick way to prove the completeness theorem (every consistant theory has a model) from the compactness theorem (a theory has a model iff every finite subtheory of it has a model)? Usually ...
1
vote
2answers
183 views

Natural and formal languages

I'm going to have to take the course Logic for Computer Science at some point and everyone says both the book and the lectures are horrible. I'm looking for a book that covers the course material in ...
1
vote
1answer
275 views

Find $\delta$ for limit

Following question and answer are from Thomas calculus book: Find a value of $\delta >0$ such that for all $0< |x-x_0|< \delta \implies a<x<b$ . we have $a=1, b=7, x_0=5$ . ...
11
votes
2answers
1k views

Do De Morgan's laws hold in propositional intuitionistic logic?

In Wikipedia page on intuitionistic logic, it is stated that excluded middle and double negation elimination are not axioms. Does this mean that De Morgan's laws, stated $$ \lnot (p \land q) \iff ...
5
votes
1answer
559 views

Mendelson's Logic book “cheats” in the propositional calculus?

In Mendelson's book ("Introduction to mathematical logic") he defines truth values for sentences in the propositional calculus using truth tables. However, it seems to me he assumes implicitly that ...
2
votes
2answers
545 views

How to interpret square brackets and valuations in propositional logic?

I am faced with this task: "Let M be the set of all valuations. Let for each propositional formula $A: [A] = v \in M : v(A) = 1$. Show that: $[A \land B] = [A] \cap [B]$ So, I get the idea what I'm ...
4
votes
3answers
291 views

Prove: $ ((A \rightarrow B) \rightarrow A) \rightarrow A ) $

How could I derive the following proposition: $$ ((A \rightarrow B) \rightarrow A) \rightarrow A ) $$ using any of the following axioms: 1) $A→(B→A)$ 2) $(A→(B→C))→((A→B)→(A→C))$ 3) ...
1
vote
1answer
110 views

Generalized “Duality” of Classical Propositional Logical Operations

Duality in propositional logic between conjunction and disjunction, $K$ and $A$ means that for any "identity", such as $KpNp = 0$ (ignoring the detail of how to define this notion in propositional ...
2
votes
2answers
1k views

Is there a systematic way to write an expression in disjunctive normal form?

Here is disjunctive normal form. http://en.wikipedia.org/wiki/Disjunctive_normal_form I understand what it is. However, I lack a systematic way of converting any complicated expression into it. For ...
2
votes
2answers
367 views

What does this question mean?

I am looking for some to explain what does this question want from me to do? Determine all true value assignments, if any, for primitive statements $p, q, r, s, t$ that make each of the following ...
1
vote
2answers
225 views

Proving a simple assertion in Propositional Logic

I have to prove some Propositional Logic assertions. Given this one: $\alpha \models \beta \Leftrightarrow (\alpha \Rightarrow \beta)$ is valid Where $\models$ is entailment The answer is: $\alpha ...
4
votes
2answers
383 views

How to write $X \iff Y$ in CNF form?

I know that $X \iff Y$ is true when $X$ is True and $Y$ is True $X$ is False and $Y$ is False I know that there is a simple algorithm to convert to CNF form, but I don't remember it...
0
votes
3answers
1k views

Express the propositional form ie. using only the NAND operator.

Recall that the NAND operator(denoted by "|") is equivalent to AND followed by negation; that is, for any two propositions a and b, the propositional form (a|b) is logically equivalent to ¬(a∧b). ...
1
vote
1answer
420 views

Expanding this boolean expression

Can this Boolean expression: $$A*\overline{A*B}$$ be expanded to give: $$A*\overline{A} * A*\overline{B}$$ Although that appears to reduce to zero? I know $A(\overline{A+B})$ can be expanded to ...