Add to a category

I've made some adjustments to your source code. First problem you were using a collection of tasks for all categories. That's why I could not properly distribute the tasks.

<div id="div-container" class="container ng-scope" ng-controller="TarefasController">
    <div class="row">
        <div class="col-xs-3">
            <!-- Ínicio Adicionar Categoria -->
            <div class="page-header">
                <h4>Adicionar Categoria</h4>
            </div>
            <div id="div-form">
                <form role="form" class="ng-pristine ng-valid">
                    <div class="form-group">
                        <input type="text" class="form-control ng-pristine ng-valid" ng-model="categoria.nome">
                    </div>
                    <button class="btn btn-info btn-block ng-pristine ng-valid" ng-click="addCategoria(categoria)" ng-model="infoIgual" ng-disabled="!categoria.nome" disabled="disabled">Adicionar</button>
                </form>
            </div>
            <!-- Fim Adicionar Categoria -->
            <!-- Ínicio Adicionar Tarefa -->
            <div class="page-header">
                <h4>Adicionar Tarefa</h4>
            </div>
            <div id="div-form">
                <form role="form" class="ng-pristine ng-valid">
                    <div class="form-group">
                        <input type="text" class="form-control ng-pristine ng-valid" ng-model="tarefa.nome">
                        <br>
                        <select class="form-control" id="category" ng-options="item.nome as item.nome for item in categorias" ng-model="categoriaSelecionada">

                        </select>
                    </div>
                    <button class="btn btn-info btn-block ng-pristine ng-valid" ng-click="addTarefa(tarefa)" ng-model="infoIgual" ng-disabled="!tarefa.nome" disabled="disabled">Adicionar</button>
                </form>
            </div>
            <!-- Fim Adicionar Tarefa -->
        </div>

        <div class="col-xs-9">
            <button class="btn btn-danger" ng-click="delTarefas()">Apagar tarefas selecionadas</button>
            <div ng-repeat="categoria in categorias">
                <h4 ng-model="categoria.selecionado">{{categoria.nome}}</h4>
                <div ng-repeat="tarefa in categoriaTarefa.tarefa[categoria.nome]">
                    <input type="checkbox" ng-model="tarefa.selecionado" ng-click="tarefaFeita()">
                    <span class="done-{{tarefa.selecionado}}">{{tarefa.nome}}</span>
                </div>
            </div>
        </div>
    </div>
</div>

angular.module('TarefApp', []);
angular.module('TarefApp').controller('TarefasController', function($scope) {
    $scope.categorias = [];
    $scope.tarefas = [];
    $scope.categoriaTarefa = {tarefa:{}};

    $scope.addTarefa = function(tarefa) {
        if(!$scope.categoriaSelecionada){
            alert("Selecione uma categoria!!!")
            return;
        }
        var c = $scope.categoriaSelecionada;

        if(!$scope.categoriaTarefa.tarefa[c])
        $scope.categoriaTarefa.tarefa[c] = [];
        else{
            var itemDuplicado = false;
            angular.forEach($scope.categoriaTarefa.tarefa[c], function (item, index){
                itemDuplicado = (item.nome === tarefa.nome);
                if(itemDuplicado){
                    alert("Tarefa para categoria já existe!");
                    return false;
                }
            });
        }

        if(!itemDuplicado){
            $scope.categoriaTarefa.tarefa[c].push(tarefa);
            $scope.tarefa = {};
        }
    };

    $scope.delTarefas = function() {
        angular.forEach($scope.categorias, function(item) {
            var c = item.nome;
            var oldTarefas = $scope.categoriaTarefa.tarefa[c];
            $scope.categoriaTarefa.tarefa[c] = [];

            angular.forEach(oldTarefas, function(tar) {
                if (!tar.selecionado) $scope.categoriaTarefa.tarefa[c].push(tar);
            });
        });
    };

    $scope.addCategoria = function(categoria) {
        angular.forEach($scope.categorias, function(item) {
            if(categoria.nome === item.nome){
                alert("A categoria já existe!");
                return;
            }
        });

        $scope.categorias.push(categoria);
        $scope.categoria = {};
    };
});