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)

2
votes
1answer
90 views

Does this proof using Novikov axiomatic propositional logic hold?

This question seems absolutely elementary but I'm having a hard time completing the proof, in fact I may have taken a bit of a left turn on it or I may be improperly applying axioms all together. ...
2
votes
1answer
343 views

How many non-equivalent formulas that use propositions p1… pn are there?

Hi I am stuck on the following question : How many non-equivalent formulas that use propositions p1...pn are there? I'm not quite sure how to find the non-equivalent formulas here, and could ...
2
votes
2answers
311 views

How to show that this logical argument is valid?

I am asked to show the following argument is valid: I know you need to use the rules of inference like modus ponens/converse fallacy but I'm confused because it doesn't look like any of the forms ...
-1
votes
2answers
459 views

Boolean Algebra - Truth Table

X'Y'Z' + XYZ I have the equation above (Boolean Algebra truth table), and as I know, if I get x' and the value of x is 0, the value will change to 1. But Y' with the top bar being higher, what ...
3
votes
2answers
938 views

How to prove logical consequence?

How do you guys prove for logical consequence? My teacher said a truth table can be done. But I don't understand how to infer from truth tables to establish logical consequences. The definition in my ...
5
votes
3answers
604 views

Could someone please explain to me how (p ∨ q) = (p NAND p) NAND (q NAND q)

I can prove it all the way to: What is the proof for those two equaling? So far I have: (p ∨ q) = (p ^ p) ∨ (q ^ q) Negate it… ~((p ^ p) ∨ (q ^ q)) You get… ~(p ^ p) ^ ~(q ^ q) = (p NAND p) ^ ...
2
votes
1answer
237 views

Why PROP (Set of all propositions) is a set by ZF axioms?

In Propositional Logic when we define the set of all propositions inductively how we can prove such a set(smallest with such properties) does exists? means that the set (of all sets with these ...
1
vote
2answers
106 views

showing logical argument is valid or invalid

showing logical argument is valid or invalid $p\to q$ $q\to (r \lor \lnot p)$ $\lnot r$ therefore, $\lnot p$ $p\to (r \lor q)$ $q\to\lnot r$ $r$ therefore, $p$ I believe (1) is valid and (2) ...
2
votes
2answers
198 views

Propositional Calculus and “Lazy evaluation”?

I want to formalize a system, and currently I don't know, if I can use propositional calculus in my case. At first, I though that I need a simple conjunction. $A \wedge B$ However, there is a ...
0
votes
2answers
204 views

Providing a counter example for a Logic Statement

How do I give a counter-example of the following logic statement (I think the statement is false): There exists $x$ $\geq$ 0 s.t. (For All real $y$, $x$ = $y$$^2$) Since the statement has a "There ...
4
votes
6answers
206 views

Propositional Logic (calculus)…stuck

Derive $c$ using: $b \implies \lnot a$ (b implies negated a) $a \land b$ (a and b) This is what I have done so far: $a \land b $ premise $b\implies -a$ premise $b$ ...
1
vote
3answers
2k views

Solve this logical puzzle only using logical equivalencies. Is there a shorter way to do it?

Here's a puzzle: Four friends have been identified as suspects for an authorized access into a computer system. They have made statements to the investigating authorities. Alice said "Carlos ...
3
votes
5answers
210 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
247 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
602 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
182 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
119 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
725 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
250 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
175 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
320 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
284 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
325 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
169 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
292 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
232 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
223 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
146 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
594 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
259 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
328 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 ...