Archive for the 'Logic' category

Introducing Three-Valued Logic

Aug 24 2010 Published by under Fuzzy Logic, Logic

So, finally, I'm getting around to three-valued logic!

To start, why are we even looking at three-valued logic? We want to get to fuzzy reasoning, and three valued logic really doesn't do the job. But it's a useful starting point, because in general, most of us have only worked with standard logics where statements are either true or false. In Fuzzy logic, we're don't have that - and that can lead to a lot of complexity. So looking at something simple that shows us how something either than "true" or "false" can actually make sense in logic.

Continue Reading »

52 responses so far

Leading in to Fuzzy Logic

Aug 05 2010 Published by under Fuzzy Logic

So, as I said in the intro to the new Scientopical Good Math/Bad Math, I'm
going to writing some articles about fuzzy logic.

Before diving into the fuzzy stuff, let's start at the beginning. What
is fuzzy logic? More fundamentally, what is logic? And what problem does fuzziness solve?

So, first, what's logic?

Logic isn't really a single thing. There are many different logics, for different purposes. But at the core, all logics have the same basic underlying concept: a logic is a symbolic reasoning system. A logic is a system for expressing statements in a form where you reason about them in a completely mechanical way, without even knowing what they mean. If you know that some collection of statements is true, using the logic, you can infer - meaning derive from a sequence of purely mechanical steps - whether or not other statements are true. If the logic is formulated properly, and you started with an initial set of true statements, then any conclusions drawn using the inference process from those statements will also be true.

When we say logic, we tend to automatically think of a particular logic: the first order predicate logic, which is the most common, fundamental logic used in both mathematics, and in rhetoric and debate. But there are an astonishing number of different logics for different purposes. Fuzzy logic is one particular
variation, which tries to provide a way of reasoning about vagueness.

Continue Reading »

94 responses so far

A Quick Bit of Temporal Logic: Introducing CTL

Apr 28 2009 Published by under Book, Logic

This post is something that I'm thinking of including in my
book. I haven't decided whether I want to spend this much time on
logics; they're really interesting and fun - but there's lots of
other interesting and fun stuff, and there's only so much space.

The topic of the moment is temporal logic - that is, a logic which
is built for reasoning about things that change over time.

To begin with, why do we want temporal logic? Most of the time,
when we want to use logical reasoning, we use predicate logic. So why
do we need another logic?

Continue Reading »

No responses yet

Mr. Spock is Not Logical (book draft excerpt)

Mar 17 2009 Published by under Logic

As I mentioned, I'll be posting drafts of various sections of my book here on the blog. This is a rough draft of the introduction to a chapter on logic. I would be extremely greatful for comments, critiques, and corrections.

I'm a big science fiction fan. In fact, my whole family is pretty
much a gaggle of sci-fi geeks. When I was growing up, every
Saturday at 6pm was Star Trek time, when a local channel show
re-runs of the original series. When Saturday came around, we
always made sure we were home by 6, and we'd all gather in front of
the TV to watch Trek. But there's one one thing about Star Trek for
which I'll never forgive Gene Roddenberry or Star Trek:
"Logic". As in, Mr. Spock saying "But that would
not be logical.".

The reason that this bugs me so much is because it's taught a
huge number of people that "logical" means the same
thing as "reasonable". Almost every time I hear anyone
say that something is logical, they don't mean that it's logical -
in fact, they mean something almost exactly opposite - that it
seems correct based on intuition and common sense.

If you're being strict about the definition, then saying that
something is logical by itself is an almost meaningless
statement. Because what it means for some statement to be
logical is really that that statement is inferable
from a set of axioms in some formal reasoning system. If you don't
know what formal system, and you don't know what axioms, then the
statement that something is logical is absolutely meaningless. And
even if you do know what system and what axioms you're talking
about, the things that people often call "logical" are
not things that are actually inferable from the axioms.

Continue Reading »

17 responses so far

What makes linear logic linear?

Jan 30 2008 Published by under Logic

Sorry for the lack of posts this week. I'm traveling for work, and
I'm seriously jet-lagged, so I haven't been able to find enough time
or energy to do the studying that I need to do to put together a solid

Fortunately, someone sent me a question that I can answer
relatively easily, even in my jet-lagged state. (Feel free to ping me with more questions that can turn into easy but interesting posts. I appreciate it!)

The question was about linear logic: specifically, what makes
linear logic linear?

Continue Reading »

No responses yet

Mathematical Constructions and the Abstraction Barrier

Nov 04 2007 Published by under Logic

There was an interesting discussion about mathematical constructions in the comment thread on my post about the professor who doesn't like infinity, and I thought it was worth turning it into a post of its own.

In the history of this blog, I've often talked about the idea of "building mathematics". I've shown several constructions - most often using something based on Peano arithmetic - but I've never really gone into great detail about what it means, and how it works.

I've also often said that the underlying theory of most modern math is built using set theory. But what does that really mean? That's the important question, and the subject of this post.

Continue Reading »

79 responses so far

The Kripke Model for Intuitionistic Logic

Mar 28 2007 Published by under Logic

As promised, today, I'm going to show the Kripke semantics model for intuitionistic logic.

Continue Reading »

5 responses so far

Kripke Semantics and Models for Intuitionistic Logic

Mar 27 2007 Published by under Logic

To be able to really talk about what a logic (or a calculus) means, you need to define a model of that logic. A model is a way of associating entities in the logic/calculus with some kind of real entity in a way where all statements in the logic about the logical entity will also be true about the real-world entity. Models are incredibly important, because it's relatively easy to design a logic which looks as if it's perfectly valid, but which contains some subtle error which leads to it being essentially meaningless - showing a model for a logic guarantees that that can't happen.

Continue Reading »

7 responses so far

Intuitionistic Logic (partial rerun)

Mar 26 2007 Published by under Logic

I'm incredibly busy right now adjusting to my new job and my new commute, which is leaving me less time than usual for blogging. So I'm going to raid the archives, and bring back some interesting things that appeared on the old Blogger blog, but were never posted here. As usual, that will involve some cleanups and rewrites, so this won't be identical to the original posts.

I've written about logic before, and mentioned intuitionistic logic at least in passing. Intuitionistic logic is an interesting subject. Intuitionistic logic is a variation of predicate logic which is built on the idea that there should be a stronger notion of "truth" in logic: that the strict categorization of all statements in classical logic as either true or false is too strong. In intuitionistic logic, a statement is only true if you can prove that it is true. It is not enough to prove that it's opposite is false: In propositional logic, it is not the case that ¬¬P→P.

Continue Reading »

17 responses so far

An Experiment with π-calculus and Programming Language Design

Mar 21 2007 Published by under Logic, Programming

I feel like a bit of a change of pace, and trying a bit of an experiment.

Re-reading Backus's old FP work reminds me of what I was doing the last time I read it, which
was back in grad school. At the time, I was working on some stuff involving parallel computation,
and I discovered Robin Milner's π-calculus as a tool for describing parallel computation. You
can think of π-calculus as being a sort of parallel (pun intended) for the λ-calculus: in
sequential, single-threaded computation, λ-calculus can be a great tool for describing what
things mean. But λ-calculus has absolutely no way of describing the concept of multiple
things happening at once. π-calculus is fundamentally built on the concept of multiple threads
which can only share information by passing messages.

There's a reason that reading Backus made me think of this, beyond just the temporal coincendence of the fact that I was working with π-calculus the last time I read Backus's
FP paper. One of the major points that Backus made was how poorly the vonNeumann model was
at describing many computations; that has become far more true in recent years. Even my laptop now has multiple processors; computation just isn't single-threaded anymore. But most programming languages are basically deeply single-threaded. Even Haskell, for all of its functional
purity, isn't particularly good at multi-threaded execution. But I've always thought it would be
a great idea to build a language around π-calculus the way that ML is built around λ-calculus.

So my experiment, such as it is, is to see if I can work through how to create an actual, useful, non-pathological programming language based on the π-calculus; and not just do that,
but do it publicly, here on the blog.

Continue Reading »

No responses yet

« Newer posts Older posts »